Problem K
Whiteboard Space

Hosuja is going to present the intended solution for an unusually tricky problem. To assist him, he has a whiteboard and a red and a blue pen. The solution he presents contains $N$ ideas to be presented in order, and each idea’s presentation requires a certain amount of whiteboard space.

Hosuja wants to use his time efficiently, which cannot be achieved if he constantly erases the whiteboard. Instead, he plans to use both his pens. It’s common knowledge that it’s perfectly fine to write two different ideas occupying the same space on a whiteboard, as long as they are written in different colors.

Figure 1: Hosuja is an experienced lectureer.

He has divided the whiteboard into $R$ rows and $C$ columns, where $1 \leq R \times C \leq 1000$. There are a total of $1 \leq N \leq 1000$ ideas, numbered from $1$ to $N$ according to the order they should be presented in. Each idea must be expressed on a single row, and idea number $i$ requires $a_ i$ columns to present for all $1 \leq i \leq N$. For each idea, Hosuja must now decide whether he wants to use the red or the blue pen.

When Hosuja presents, he will write down the ideas in reading order. That is, he starts at the top of the whiteboard from the left. If there is no space left on the current row he is writing on for the entire next idea, he will switch rows and never return to this row with the color he is currently using. Each time he switches colors, he will continue where he left off the last time he used this color. He can switch colors in betweend different ideas, and he can do so as many times as he wants.

Now he wonders how many ideas he can write down before he is forced to erase the whiteboard, given that he chooses an optimal color division for the ideas.

Input

The first line contains the numbers $N$, the number of ideas, and $R$ and $C$, the number of rows and columns the whiteboard is divided into. Then follows a line with the $N$ numbers $a_1, a_2, ..., a_ N$, where $1 \leq a_ i \leq C$ describes the number of columns idea number $i$ needs to be presented for all $1 \leq i \leq N$.

Output

Write a single number: The number of ideas Hosuja can present before he has to erase the whiteboard.

Scoring

Your solution will be tested on various test groups. To score points for a group, you must pass all the test cases in that group.

Explanation of test case 2

Figure 2: If he chooses to use colors in the order R,B,R,RB,B he is able to fit the first $6$ ideas on the whiteboard.

5 1 4
1 2 3 2 1

4

8 2 10
8 1 2 10 9 9 2 4

6