[ABC085D] Katana Thrower

题面翻译

有一个血量值为h的怪物，你有n把刀，每把刀可以用来砍和飞（飞的就不能再用了），刀i分别有两种伤害砍ai和飞bi。无论是砍还是飞都算操作一次，问杀掉怪物最少需要多少次操作。

感谢@chengni 提供的翻译

题目描述

あなたが散歩していると、突然一体の魔物が出現しました。幸い、あなたは $N$ 本の刀、刀 $1$、刀 $2$、$…$、刀 $N$ を持っていて、次の二種類の攻撃を自由な順番で行うことができます。

• 持っている刀のうち一本を振る。刀 $i$ $(1\ <\ =\ i\ <\ =\ N)$ を振ると、魔物は $a_i$ ポイントのダメージを受ける。同じ刀を何度振ることもできる。
• 持っている刀のうち一本を投げつける。刀 $i$ $(1\ <\ =\ i\ <\ =\ N)$ を投げつけると、魔物は $b_i$ ポイントのダメージを受け、あなたはその刀を失う。すなわち、あなたは以後その刀を振ることも投げつけることもできなくなる。

魔物は、受けたダメージの合計が $H$ ポイント以上になると消滅します。魔物を消滅させるには、最小で合計何回の攻撃が必要でしょうか。

输入格式

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

$N$ $H$ $a_1$ $b_1$ $:$ $a_N$ $b_N$

输出格式

魔物を消滅させるために必要な最小の合計攻撃回数を出力せよ。

样例 #1

样例输入 #1

1 10
3 5

样例输出 #1

3

样例 #2

样例输入 #2

2 10
3 5
2 6

样例输出 #2

2

样例 #3

样例输入 #3

4 1000000000
1 1
1 10000000
1 30000000
1 99999999

样例输出 #3

860000004

样例 #4

样例输入 #4

5 500
35 44
28 83
46 62
31 79
40 43

样例输出 #4

9

提示

制約

• $1\ <\ =\ N\ <\ =\ 10^5$
• $1\ <\ =\ H\ <\ =\ 10^9$
• $1\ <\ =\ a_i\ <\ =\ b_i\ <\ =\ 10^9$
• 入力値はすべて整数である。

Sample Explanation 1

あなたは $1$ 本の刀を持っていて、振ると $3$ ポイントのダメージ、投げつけると $5$ ポイントのダメージを与えられます。刀を $2$ 回振ってから投げつけると $3\ +\ 3\ +\ 5\ =\ 11$ ポイントのダメージを与え、合計 $3$ 回の攻撃で魔物が消滅します。

Sample Explanation 2

先ほどの刀に加えてもう $1$ 本別の刀もあり、こちらは振ると $2$ ポイントのダメージ、投げつけると $6$ ポイントのダメージを与えられます。両方の刀を投げつけると $5\ +\ 6\ =\ 11$ ポイントのダメージを与え、$2$ 回の攻撃で魔物が消滅します。