题目描述

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

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

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

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

输入格式

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

$N$ $H$ $t_1$ $d_1$ $\vdots$ $t_N$ $d_N$

输出格式

答えを出力せよ。

题目大意

有一只血量为 $H$ 的怪兽，你现在要攻击它。你有 $N$ 种方式可以攻击它。

如果你在时间 $j$ 用了第 $i$ 种方式攻击，那么在时间 $j,j+1,\cdots j+t_i-1$，它都会受到 $d_i$ 点伤害。

问最少需要花多少时间才能使怪兽的血量不高于 $0$。

2 20
2 2
5 1

6

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

9

提示

制約

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

Sample Explanation 1

以下のようにするとターン $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$ になる。