Score : 400 points
You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have N katana (swords), Katana 1, Katana 2, …, Katana N, and can perform the following two kinds of attacks in any order:
The monster will vanish when the total damage it has received is H points or more. At least how many attacks do you need in order to vanish it in total?
Input is given from Standard Input in the following format:
N H a_1 b_1 : a_N b_N
Print the minimum total number of attacks required to vanish the monster.
1 10 3 5
3
You have one katana. Wielding it deals 3 points of damage, and throwing it deals 5 points of damage. By wielding it twice and then throwing it, you will deal 3 + 3 + 5 = 11 points of damage in a total of three attacks, vanishing the monster.
2 10 3 5 2 6
2
In addition to the katana above, you also have another katana. Wielding it deals 2 points of damage, and throwing it deals 6 points of damage. By throwing both katana, you will deal 5 + 6 = 11 points of damage in two attacks, vanishing the monster.
4 1000000000 1 1 1 10000000 1 30000000 1 99999999
860000004
5 500 35 44 28 83 46 62 31 79 40 43
9