Snuke 有 $N$ 张写有数字的卡片。第 $i$ 张卡片上的数字为正整数 $a_i$，颜色为 $c_i$（在本题中，我们用整数表示颜色）。

Snuke 对这些卡片的配色方案有如下假设：

• 数字在 $1 \le a_i \le M$ 范围内的卡片颜色相同。
• 数字在 $M + 1 \le a_i \le 2M$ 范围内的卡片颜色相同，且该颜色与 $1 \le a_i \le M$ 范围内的卡片颜色不同。
• 数字在 $2M + 1 \le a_i \le 3M$ 范围内的卡片颜色相同，且该颜色与 $1 \le a_i \le 2M$ 范围内的卡片颜色不同。
• 数字在 $3M + 1 \le a_i \le 4M$ 范围内的卡片颜色相同，且该颜色与 $1 \le a_i \le 3M$ 范围内的卡片颜色不同。
• 以此类推。

有多少个正整数 $M$ 符合他手中所有卡片的配色情况？如果 $M$ 的可能性有无穷多种，请输出 $-1$。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 20$)。接下来 $N$ 行，每行包含两个整数 $a_i$ 和 $c_i$，分别表示 Snuke 的一张卡片上的数字和颜色 ($1 \le a_i \le 10^9$, $1 \le c_i \le 20$)。保证序列 $a_i$ 是严格递增的。

输出格式

在一行中输出答案。

样例

样例输入 1

4
27 2
2000 4
2015 4
2100 1

样例输出 1

277

样例输入 2

3
1 1
2 2
3 1

样例输出 2

0