F - 番号札 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

すぬけ君が番号札を N 個持っている。i 番目の番号札には数字 a_i が書いてあり、色は c_i である。

すぬけ君は、ある正整数 M が存在し、数字と色の間には以下のような関係があるのではないかと考えた。

  • 1,\ ...,\ M は同じ色で塗られている。
  • M+1,\ ...,\ 2M は別の同じ色で塗られている。
  • 2M+1,\ ...,\ 3M は別の同じ色で塗られている。
  • ...

M として何通りの数が考えられるか求めよ。ただし、M の値が無限通り考えられる場合には、-1 を出力せよ。

Constraints

  • 1 \leq N \leq 20
  • 1 \leq a_1 < ... < a_N \leq 10^9
  • 1 \leq c_i \leq 20

Input Format

入力は以下の形式で標準入力から与えられる。 
N
a_1 c_1
:
a_N c_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4
27 2
2000 4
2015 4
2100 1

Sample Output 1

277

Sample Input 2

3
1 1
2 2
3 1

Sample Output 2

0