Problem G
Trick and Treat
During Halloween, kids come by your house to request candy. If you can not give them any, they will become angry and throw toilet paper at your house!
This year, you have already scouted the neighbourhood and know that kids will come to your house in groups of $A_1, A_2, \dots , A_ N$ kids in that order. When a group of $A_ i$ kids comes, they will request $A_ i$ pieces of candy. If you do not have enough, they throw a roll of toilet paper and move on to the next house, never to return again. Otherwise, you will give them the candy and wait for the next group of kids.
You now wonder, if you have a budget that allows you to buy $M$ pieces of candy, how many should you buy in order to get as few as possible rolls of toilet paper thrown at you?
Input
The first line of input contains two numbers $1 \le N \le 100\, 000$ and $1 \le M \le 2 \cdot 10^9$ – the number of group of kids that will come, and the maximum amount of candy that you can buy.
The next $N$ lines contains the sizes of the groups of kids that will come to your house, in the order that they arrive. Each group of kids will request between $1$ and $10$ pieces of candy.
Output
Output a single integer – the fewest possible rolls of toilet paper you can have thrown at you, if you buy the right amount of candy.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
1 |
50 |
$M$ and $N$ will be at most $100$. |
|
2 |
150 |
No further constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 3 2 1 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 1 1 2 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 5 2 1 1 4 3 2 5 |
4 |
