1649 . 人生就是不停的戰鬥 (RPG)
TopCoder
Tags
Description
有這麼一句話：『人生就像一場RPG，只不過死亡之後不能在儲存點復活。』
現在你正處於這個恐怖的RPG 中名為學校的一個關卡，你必須想辦法度過種種難關。
透過傳說中的NPC(老師、同學等)，你得知在前方依序共有n 隻怪獸(考試、作業等)，你必須要打倒他們，才能獲得通關證明(畢業證書等)。
只是，打倒他們是會損耗你的血量的，如果你的血量不大於零，就會失去戰鬥力，從這個關卡中出局。
不過，既然是RPG 一定有補血的道具(寫ACM,USACO,TIOJ)，而且一次就可以補滿血，只不過，雖然補血不需要花費金錢，但礙於遊戲的限制，
補越多次血，分數就會越低，因此你希望補血的次數盡量的少。
現在你已經知道每隻怪獸會損耗你多少血量，以及你自己的血量，就你最少要補多少次血才能度過難關呢？
Input Format
第一行有兩個數字：n 以及health，其中n 代表怪獸的數量，health 代表你滿血時的血量
第二行有n 個數字以空白隔開，代表每隻怪獸會對你造成的傷害。
Output Format
請輸出一個數字：k，代表要度過難關，最少使用k 次補血道具。
若無法度過難關，請輸出一個數字-1。
Sample Input 1
3 100
99 99 99
99 99 99
Sample Output 1
2
Sample Input 2
1 100
2147483647
2147483647
Sample Output 2
-1
Hints
對於所有測試資料，血量永遠為正整數，另外，怪獸所造成的傷害與滿血時的血量值皆在INT64的範圍之內。
Problem Source
原TIOJ1649 / 98建中校內資訊能力競賽(prob1)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |