No.187 中華風 (Hard)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : LayCurseLayCurse

3 ProblemId : 448 / 出題時の順位表

問題文

諸外国では,○+□=8のように,答えがたくさんある問題があるようですが,採点が大変ですよね.
今度は,中華風にアレンジしてみましょう.

$N$ 個の整数の $2$ つ組 $(X_1, Y_1),(X_2, Y_2), \ldots ,(X_N, Y_N)$ が与えられるので,
  □ ${\rm mod}\ Y_k = X_k, \quad k=1,2,\ldots,N$
を同時に満たす□に当てはまる正整数を求めてください.
あれ,これは,答えがたくさんあるかもしれません.
その場合は,最も小さいものを求めてください.
最も小さいものでも大きい数になるかもしれないので,答えを $10^9+7$ で割った余りだけ答えてください.

入力

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

$1 \leq N \leq 1000$
$0 \leq X_i < Y_i \leq 1000000000 = 10^9$

出力

□にあてはまる最小の正整数を $10^9+7$ で割った余りを出力してください。
ただし,存在しないなら,$\verb|-1|$ を代わりに出力してください.

サンプル

サンプル1
入力
3
10 20
10 30
10 40
出力
10

$20$ で割っても,$30$ で割っても,$40$ で割っても $10$ 余るなんて,もうこれは $10$ でしょ.

サンプル2
入力
3
10 20
10 30
30 40
出力
70

$20$ で割っても,$30$ で割っても $10$ 余るなんて…,あ,$70$ でした.

サンプル3
入力
3
1 2
0 4
5 17
出力
-1

$2$ で割り切れないので,$4$ で割り切れることはないのでは?

提出ページヘ