持续伤害

题目描述

一个体力为 $H$ 的怪物出现在你面前,回合制战斗开始了。

在每个回合 $1,2,\ldots$ 中,你施放 $N$ 种法术(法术 $1,\ldots,N$)中的一种。

如果你在第 $j$ 回合施放法术 $i$,怪物的体力会在第 $j,j+1,\ldots,j+t_i-1$ 的每个回合中减少 $d_i$。

求最早能使怪物体力变为 $0$ 或以下的回合。

输入格式

输入按以下格式从标准输入给出:

N H
t_1 d_1
⋮
t_N d_N

输出格式

输出答案。

样例

2 20
2 2
5 1

6

以下过程在第 $6$ 回合使怪物的体力变为 $0$ 或以下,这是最早的。

第 $1$ 回合施放法术 $1$。由于第 $1$ 回合施放的法术,怪物的体力减少 $2$,变为 $18$。

第 $2$ 回合施放法术 $2$。由于第 $1$ 和第 $2$ 回合施放的法术,怪物的体力减少 $2+1=3$,变为 $15$。

第 $3$ 回合施放法术 $1$。由于第 $2$ 和第 $3$ 回合施放的法术,怪物的体力减少 $1+2=3$,变为 $12$。

第 $4$ 回合施放法术 $2$。由于第 $2,3$ 和第 $4$ 回合施放的法术,怪物的体力减少 $1+2+1=4$,变为 $8$。

第 $5$ 回合施放法术 $1$。由于第 $2,4$ 和第 $5$ 回合施放的法术,怪物的体力减少 $1+1+2=4$,变为 $4$。

第 $6$ 回合施放法术 $2$。由于第 $2,4,5$ 和第 $6$ 回合施放的法术,怪物的体力减少 $1+1+2+1=5$,变为 $-1$。

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

9

数据范围

• $1 \le N \le 3 \times 10^5$
• $1 \le H \le 10^{18}$
• $1 \le t_i,d_i \le 10^9$
• 输入中的所有值均为整数。