Space Voyage

题意翻译

### 题目描述 ABBYY 的那只小河狸要在一个超现代的宇宙飞船上来一次太空旅行。在这次旅行中，他计划要去 $n$ 个星球上玩。对于第 $i$ 个星球，那个星球的外星人允许从别的星球来的旅客最多携带 $a_i$ 个旅行箱，而那个星球总共有 $b_i$ 个原住民。 小河狸想给旅行途径的星球上的居民送一些从 ABBYY 带来的土特产。这些土特产都被装在了旅行箱里，每个旅行箱里都有 $x$ 个土特产。小河狸总共会带 $\sum_{i=1}^{n}a_i$ 个旅行箱到宇宙飞船上。 小河狸到达第 $i$ 个星球时，他会从飞船上拿出 $a_i$ 个旅行箱。第一天，小河狸会在星球上瞎逛悠，和原住民交交朋友。在之后他在星球上旅游的每一天他都会给星球上的 $b_i$ 个原住民带一个土特产。当他带到星球上的礼物不足以给每人都分一个的时候，他就会离开这个星球，而剩下的礼物全被丢到宾馆里去了。 小河狸总共想花 $c$ 天时间来履行。由于科技很发达，小河狸乘坐的飞船可以瞬间到达任意一个星球。请你帮小河狸求出有多少个正整数 $x$ 可以使得旅行的总时长为 $c$ 天。 --- ### 输入格式 输入数据的第一行包含用单个空格隔开的两个整数 $n$ 和 $c$，分别代表小河狸要造访的星球数和小河狸想要的旅行计划的总时长。 接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $b_i$，分别代表小河狸能带到第 $i$ 个星球的旅行箱总数和第 $i$ 个星球的原住民总数。 **温馨小提示** ：推荐使用 64 位整型进行运算。某些解法中，你的中间结果甚至可能会超出 64 位整型的范围。悠着点儿乘！ --- ### 输出格式 你的输出应包含一个整数 $k$，代表能使总旅游天数为 $c$ 天的$x$的数量。如果有无限个 $x$ 均能使总旅游天数为 $c$ 天，则输出 `-1`。 **温馨小提示** ：不推荐在 C++ 语言中使用 `%lld` 来读写 64 位整型。我们推荐使用**输入输出流**和 `%I64d`。 --- ### 数据范围 | # | 数据得分 | 数据范围 | 特殊性质 | | ----------- | ----------- | ----------- | ----------- | | $1$ | $30$ | $1\leq n\leq 100$；$1\leq a_i,\ b_i, \ c\leq 10^3$ | | | $2$ | $100$ | $1\leq n\leq 10^4$；$1\leq a_i,\ b_i, \ c\leq 10^9$ | | --- ###### Translated by \_FILARET\_

题目描述

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?

输入输出格式

输入格式

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<=10^{4} $ - $ 0<=a_{i}<=10^{9} $ - $ 1<=b_{i}<=10^{9} $ - $ 1<=c<=10^{9} $ 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!

输出格式

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.

输入输出样例

输入样例 #1

2 5
1 5
2 4

输出样例 #1

1

说明

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.