题目描述
小蓝正在玩一个植物大战僵尸的改版,在一个特别的关卡中,他需要用玉米大炮击溃僵王博士。
现在小蓝已经部署了 nnn 个玉米大炮,对于第 iii 个玉米大炮,有一个伤害值 aia_iai ,一个装填时间 bib_ibi ,玉米大炮每次发射后需要 bib_ibi 的装填时间,装填完毕之后才可以再次发射。
小蓝已经知道僵王博士有 mmm 点生命值,但他不知道他什么时间可以击溃僵王博士,你需要计算出出小蓝最少需要多少时间可以击溃僵王博士。
小蓝可以同时控制所有玉米大炮, 玉米大炮每次对僵王博士的攻击会扣除等于其伤害值的血量,如果血量低于或者等于 000 ,僵王博士被消灭,僵王博士被永久冻结不会攻击,开始时所有玉米大炮都装填完毕,装填完毕后小蓝会直接控制其立即攻击,攻击所花费的时间忽略不计。
输入
第一行两个个整数 nnn , mmm (1≤n≤105,1≤m≤109)( 1 \le n \le 10^{5} , 1 \le m \le 10^{9} )(1≤n≤105,1≤m≤109)。
接下来 nnn 行,每行两个整数 aia_iai , bib_ibi (1≤ai≤109,1≤bi≤109)(1 \le a_i \le 10^{9} , 1 \le b_i \le 10^{9})(1≤ai≤109,1≤bi≤109)。
输出
输出一行一个整数,代表击溃僵王博士需要的最小时间。
样例输入 Copy
3 3
1 1
2 2
3 3
样例输出 Copy
0