User's AC Ratio

88.2% (15/17)

Submission's AC Ratio

38.6% (17/44)

Description

有這麼一句話:『人生就像一場RPG,只不過死亡之後不能在儲存點復活。』

現在你正處於這個恐怖的RPG 中名為學校的一個關卡,你必須想辦法度過種種難關。

透過傳說中的NPC(老師、同學等),你得知在前方依序共有n 隻怪獸(考試、作業等),你必須要打倒他們,才能獲得通關證明(畢業證書等)。

只是,打倒他們是會損耗你的血量的,如果你的血量不大於零,就會失去戰鬥力,從這個關卡中出局。

不過,既然是RPG 一定有補血的道具(寫ACM,USACO,TIOJ),而且一次就可以補滿血,只不過,雖然補血不需要花費金錢,但礙於遊戲的限制,
補越多次血,分數就會越低,因此你希望補血的次數盡量的少。

現在你已經知道每隻怪獸會損耗你多少血量,以及你自己的血量,就你最少要補多少次血才能度過難關呢?

Input Format

第一行有兩個數字:n 以及health,其中n 代表怪獸的數量,health 代表你滿血時的血量
第二行有n 個數字以空白隔開,代表每隻怪獸會對你造成的傷害。

Output Format

請輸出一個數字:k,代表要度過難關,最少使用k 次補血道具。
若無法度過難關,請輸出一個數字-1。

Sample Input

Sample Input #1
3 100
99 99 99

Sample Input #2
1 100
2147483647

Sample Output

Sample Output #1
2

Sample Output #2
-1

Hints

對於所有測試資料,血量永遠為正整數,另外,怪獸所造成的傷害與滿血時的血量值皆在INT64的範圍之內。

Problem Source

原TIOJ1649 / 98建中校內資訊能力競賽(prob1)

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144