Kostya 正在玩电脑游戏 Cookie Clicker。这个游戏的目标是收集饼干。你可以使用不同的建筑物来获得饼干:你只需点击屏幕上的一个特殊字段并通过点击获得饼干,你可以购买饼干工厂,炼金术实验室,时间机器,这一切都会带来很多很多饼干。
在游戏开始时(时间 0),Kostya 有 0 块饼干并且没有建筑物。他有 n 个可用的建筑物可供选择:第 i 个建筑物值得 ci 饼干,当它建成时,它会在每一秒结束时带来 vi 饼干。另外,为了让游戏玩起来更有趣,Kostya决定添加一个限制:在每个时刻,他只能使用一栋建筑。当然,他可以自行决定每秒更改活动建筑物。
重要的是,Kostya 正在玩一个游戏版本,他只能在一秒的倍数时刻购买新建筑物并更改活动建筑物。 Kostya 可以购买新建筑并同时使用它。如果Kostya在t时刻开始使用建筑物,那么他只有在t+1时刻才能从中获得第一笔利润。
Kostya 希望尽快赚取至少 s 块饼干。确定他需要多少秒来完成该操作。
输入
第一行包含两个整数 n 和 s (1 ≤ n ≤ 2·105, 1 ≤ s ≤ 1016) - 游戏中的建筑物数量和 Kostya 想要获得的饼干数量。
接下来的 n 行中的每一行都包含两个整数 vi 和 ci (1 ≤ vi ≤ 108, 0 ≤ ci ≤ 108) - 第 i 栋建筑每秒带来的 cookie 数量以及该建筑的价格。
输出
输出唯一的整数——Kostya 至少需要多少秒才能获得 s cookie。保证他能做到。
示例
输入 #1
3 9 1 0 2 3 5 4
输出 #1
6
输入 #2
3 6 1 0 2 2 5 4
输出 #2
5
输入 #3
3 13 1 0 2 2 6 5
输出 #3
7
输入#4
1 10000000000000000 1 0
输出#4
10000000000000000