ABBYY 的智能海狸计划乘坐超现代宇宙飞船进行太空旅行。在航行期间他计划访问n个行星。对于行星 i,ai 是允许外星游客携带到该行星的最大手提箱数量,bi 是该行星上的公民数量。
智能海狸将把 ABBYY 的一些礼物带到他将要访问的行星。礼物装在手提箱里,每个手提箱里有 x 件礼物。海狸号将携带 a1 + ... + 一个手提箱上船。
当海狸登陆第i颗行星时,他带着ai手提箱出去了。在来到这个星球的第一天,海狸会去散步并了解这里的居民。在第二天以及随后的所有日子里,海狸都会向公民赠送礼物——每个双性公民每天都会收到一份礼物。海狸会在当天晚上离开地球,此时剩余的礼物数量严格少于公民数量(即,一旦他第二天无法赠送适当数量的礼物)。他把剩下的礼物留在了酒店。
海狸将花费正好 c 天的时间旅行。在行星之间飞行所花费的时间被认为是零。有多少种方法可以选择正整数 x 以使计划航程恰好需要 c 天?
输入
第一输入行包含空格分隔的整数 n 和 c — 海狸将要访问的行星数量以及他将相应旅行的天数。
接下来的 n 行包含一对以空格分隔的整数 ai, bi (1 ≤ i ≤ n) — 相应地,他可以带到第 i 个星球的手提箱数量和第 i 个星球的公民数量。
获得 30 点的输入限制为:
- 1 ≤ n ≤ 100
- 1 ≤ ai ≤ 100
- 1 ≤ bi ≤ 100
- 1 ≤ c ≤ 100
获得 100 点的输入限制为:
- 1 ≤ n ≤ 104
- 0 ≤ ai ≤ 109
- 1 ≤ bi ≤ 109
- 1 ≤ c ≤ 109
由于可能发生溢出,建议使用64位运算。在某些解决方案中,甚至 64 位算术也可能溢出。所以计算时要小心!
输出
打印一个数字 k — 选择 x 以便旅行恰好 c 天的方式数。如果 x 有无限多个可能的值,则打印 -1。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
2 5 1 5 2 4
输出 #1
1
注意
在第一个示例中,只有一个合适的值 x = 5。然后海狸带着 1 个手提箱,里面有 5 件礼物到第一个行星。他在这里待了两天:第一天他闲逛,第二天他送出五件礼物。他带着2个手提箱和10件礼物来到第二颗行星。他在这里度过了 3 天——他在第二天和第三天赠送了 4 件礼物,并将剩下的 2 件礼物留在了酒店。海狸总共花了 5 天的时间旅行。
当 x = 4 或更少时,海狸在第一个行星上的第二天将没有足够的礼物,因此航行将很快结束。当 x = 6 或更多时,海狸将在第二颗行星上至少多呆一天,并且航程将花费太长时间。