Coding Cup @Google 2019

Start

2019-11-01 17:00 UTC

Coding Cup @Google 2019

End

2019-11-01 18:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -39 days 7:10:54

Time elapsed

1:30:00

Time remaining

0:00:00

Problem A
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