Woburn Challenge 2018-19 Round 2 - Junior Division

Ethan Hunt is really in the thick of things now — having infiltrated escaped convict Solomon Lane's hideout in the Rocky Mountains, he's now found himself surrounded by ~N~ ~(1 \le N \le 1\,000)~ of Solomon's guards, with but a single tranquilizer gun to defend himself!

The tranquilizer gun can hold up to ~M~ ~(1 \le M \le 1\,000)~ bullets at a time, and Ethan initially has it loaded with ~S~ ~(0 \le S \le M)~ bullets.

Hitting a guard with a single bullet is enough to tranquilize them, and of course, Ethan never misses. The problem is, he might simply not have enough bullets to tranquilize all of the guards. Fortunately, a potential solution has occurred to Ethan — some of the guards appear to be carrying bullets compatible with his gun, which he might be able to grab and use for himself!

The ~i~-th guard is carrying ~B_i~ ~(0 \le B_i \le 1\,000)~ bullets, which they'll drop upon being tranquilized. This means that, if Ethan chooses to use up a bullet to tranquilize the ~i~-th guard, he can then load up to ~B_i~ new bullets into his tranquilizer gun immediately afterwards. However, he may only use a number of new bullets which will not cause his gun's new bullet count to exceed ~M~. He also may not leave excess bullets lying around and load them into his gun later on, as they'll get lost amidst the chaotic firefight.

Ethan may tranquilize ~0~ or more of the ~N~ guards in any order he'd like, as long as he always has at least one bullet available in his gun to tranquilize the next guard. What's the maximum number of guards who he can tranquilize?

Subtasks

In test cases worth ~16/40~ of the points, ~N \le 10~ and ~M = 1\,000~.
In test cases worth another ~14/40~ of the points, ~M = 1\,000~.

Input Specification

The first line of input consists of three space-separated integers, ~N~, ~M~, and ~S~.
~N~ lines follow, the ~i~-th of which consists of a single integer, ~B_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the maximum number of guards who Ethan can tranquilize.

Sample Input 1

3 1000 1
0 1 2

Sample Output 1

3

Sample Input 2

6 2 2
1 0 0 3 0 0

Sample Output 2

5

Sample Explanation

In the first case, Ethan could first choose to tranquilize the ~2~nd guard, using up his only bullet but then picking up another bullet. He could then use that bullet to tranquilize the ~3~rd guard, picking up two new bullets as a result. Finally, he could use one of those bullets to tranquilize the ~1~st guard.

In the second case, Ethan could choose to tranquilize guards ~1~, ~2~, ~4~, ~3~, and ~6~, in that order. This would leave him with no bullets remaining to tranquilize the ~5~th guard, but tranquilizing ~5~ out of the ~6~ guards is the best he can do.