You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

apiadu 有一个非负整数 $x$，已知 $n$ 个条件：这个数模 $a_i$ 的余数为 $b_i$。

请你求出这个数 $x$ 最小的可能值是多少。

特别的，如果答案 $x$ 超过 $10^4$，请输出 $-1$。

格式

输入格式

第一行包含一个整数 $n$，表示条件的个数。

接下来的 $n$ 行，每行包含两个整数，表示 $a_i$ 和 $b_i$。

输出格式

输出一行一个整数，表示答案。如果答案超过 $10^4$ 那么输出 $-1$。

样例

样例输入 #1

3
3 1
5 1
7 2

样例输出 #1

16

样例解释 #1

$16 \bmod 3 = 1$，$16 \bmod 5 = 1$，$16 \bmod 7 = 2$。

且 $16 \le 10000$，符合题意。

可以证明不存在比 $16$ 更小的非负整数满足答案。

样例输入 #2

2
10000 9999
9999 9998

样例输出 #2

-1

数据规模

对于 $100\%$ 的数据，$1 \le n \le 10^3$，$0 \le b_i < a_i \le 10^4$。