← 返回题目列表

Codeforces · 377/E

E. 饼干点击器

中文机器翻译题面 查看原题

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