配点 : $525$ 点

問題文

あなたの前に体力 $H$ のモンスターが現れ、ターン制の戦闘が開始しました。

あなたは、ターン $1,2, \cdots$ のそれぞれに呪文 $1, \cdots ,N$ の $N$ 種類の呪文のうち一つを唱えます。

ターン $i$ に呪文 $j$ を唱えると、その呪文の効果としてターン $i,i+1, \cdots ,i+t_j -1$ のそれぞれでモンスターの体力が $d_j$ 減ります。

モンスターの体力を $0$ 以下にすることが可能な最も早いターンを求めてください。

制約

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq H \leq 10^{18}$
• $1 \leq t_i,d_i \leq 10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $H$

$t_1$ $d_1$

$\vdots$

$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