CF177E2 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\_