CF177E1.Space Voyage

The Smart Beaver from ABBYY plans a space travel on an ultramodern spaceship. During the voyage he plans to visit n planets. For planet i a__i is the maximum number of suitcases that an alien tourist is allowed to bring to the planet, and b__i is the number of citizens on the planet.

The Smart Beaver is going to bring some presents from ABBYY to the planets he will be visiting. The presents are packed in suitcases, x presents in each. The Beaver will take to the ship exactly _a_1 + ... + a__n suitcases.

As the Beaver lands on the i-th planet, he takes a__i suitcases and goes out. On the first day on the planet the Beaver takes a walk and gets to know the citizens. On the second and all subsequent days the Beaver gives presents to the citizens — each of the b__i citizens gets one present per day. The Beaver leaves the planet in the evening of the day when the number of presents left is strictly less than the number of citizens (i.e. as soon as he won't be able to give away the proper number of presents the next day). He leaves the remaining presents at the hotel.

The Beaver is going to spend exactly c days traveling. The time spent on flights between the planets is considered to be zero. In how many ways can one choose the positive integer x so that the planned voyage will take exactly c days?

ABBYY 的聪明海狸计划乘坐一艘超现代宇宙飞船进行太空旅行。在旅途中，他计划访问 $n$ 颗行星。对于第 $i$ 颗行星，$a_i$ 表示外星游客被允许带入该行星的行李箱最大数量，$b_i$ 表示该行星上的公民人数。

聪明海狸将从 ABBYY 带一些礼物前往他将要访问的行星。这些礼物被装在行李箱中，每个行李箱装 $x$ 件礼物。海狸将恰好携带 $a_1 + \dots + a_n$ 个行李箱登上飞船。

当海狸降落在第 $i$ 颗行星时，他会取出 $a_i$ 个行李箱并下船。在该行星的第一天，海狸外出散步，结识当地公民。从第二天起及之后的每一天，海狸都会向公民分发礼物——每天每位 $b_i$ 名公民各获得一件礼物。海狸将在当天傍晚离开该行星，条件是：此时剩余礼物数严格小于公民人数（即，从第二天起他将无法再为每位公民都分发一件礼物）。他把剩余的礼物留在酒店。

海狸整个旅行将恰好持续 $c$ 天。行星之间的飞行时间视为零。问：有多少种选择正整数 $x$ 的方式，使得此次计划中的航行恰好持续 $c$ 天？

The first input line contains space-separated integers n and c — the number of planets that the Beaver is going to visit and the number of days he is going to spend traveling, correspondingly.

The next n lines contain pairs of space-separated integers a__i, b__i (1 ≤ i ≤ n) — the number of suitcases he can bring to the i-th planet and the number of citizens of the i-th planet, correspondingly.

The input limitations for getting 30 points are:

• 1 ≤ n ≤ 100
• 1 ≤ a__i ≤ 100
• 1 ≤ b__i ≤ 100
• 1 ≤ c ≤ 100

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 104
• 0 ≤ a__i ≤ 109
• 1 ≤ b__i ≤ 109
• 1 ≤ c ≤ 109

Due to possible overflow, it is recommended to use the 64-bit arithmetic. In some solutions even the 64-bit arithmetic can overflow. So be careful in calculations!

第一行输入包含两个以空格分隔的整数 $n$ 和 $c$ —— 分别表示海狸将要访问的星球数量以及他用于旅行的天数。

接下来的 $n$ 行，每行包含一对以空格分隔的整数 $a_i,\,b_i$（$1 \le i \le n$）—— 分别表示海狸可携带至第 $i$ 个星球的行李箱数量，以及第 $i$ 个星球的公民数量。

获取 30 分的输入限制为：

• $1 \le n \le 100$
• $1 \le a_i \le 100$
• $1 \le b_i \le 100$
• $1 \le c \le 100$

获取 100 分的输入限制为：

• $1 \le n \le 10^4$
• $0 \le a_i \le 10^9$
• $1 \le b_i \le 10^9$
• $1 \le c \le 10^9$

由于可能发生整数溢出，建议使用 64 位整数运算。在某些解法中，即使使用 64 位整数运算仍可能溢出，因此请在计算时格外谨慎！

Print a single number k — the number of ways to choose x so as to travel for exactly c days. If there are infinitely many possible values of x, print -1.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

输出一个整数 k —— 表示选择 x 使得恰好旅行 c 天的方案数。若满足条件的 x 有无穷多个，则输出 -1。

请注意：在 C++ 中，请勿使用 %lld 说明符读写 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first example there is only one suitable value x = 5. Then the Beaver takes 1 suitcase with 5 presents to the first planet. Here he spends 2 days: he hangs around on the first day, and he gives away five presents on the second day. He takes 2 suitcases with 10 presents to the second planet. Here he spends 3 days — he gives away 4 presents on the second and the third days and leaves the remaining 2 presents at the hotel. In total, the Beaver spends 5 days traveling.

For x = 4 or less the Beaver won't have enough presents for the second day on the first planet, so the voyage will end too soon. For x = 6 and more the Beaver will spend at least one more day on the second planet, and the voyage will take too long.

在第一个例子中，只有一个合适的值 $x = 5$。此时，海狸携带 1 个装有 5 件礼物的行李箱前往第一颗行星。他在那里花费 2 天时间：第一天闲逛，第二天送出全部 5 件礼物。接着，他携带 2 个共装有 10 件礼物的行李箱前往第二颗行星。在那里他花费 3 天时间——在第二天和第三天各送出 4 件礼物，并将剩余的 2 件礼物留在旅馆。总计，海狸此次旅行共花费 5 天。

当 $x \leq 4$ 时，海狸在第一颗行星的第二天没有足够的礼物可送，因此旅程会过早结束；当 $x \geq 6$ 时，海狸在第二颗行星至少还需多待一天，导致整个旅程耗时过长。