Recording Songs#810
During a music concert broadcast, entrepreneur decided to start a business producing cassettes. He has cassettes, each with a playback capacity of , and wants to record as many songs as possible on them. There are songs, transmitted in order 1, 2, \ldots, N, each with a known duration: L(1), L(2), \ldots, L(N). The entrepreneur can make the following choices:
Record the next song on the current cassette (if it fits) or skip it;
If the song does not fit on the current cassette, skip the song or start recording it on a new cassette. In this case, the old cassette is set aside and cannot be used further.
Determine the maximum number of songs the entrepreneur can record on the cassettes.
The first line contains the number (M \leq 200).
The second line contains (D \leq 10^9).
The third line contains (N \leq 500).
The fourth line contains L(1), L(2), \ldots, L(N). Each L(i) \leq D.
All input values are natural numbers.
Output a single integer, the maximum number of songs that can be recorded.
Example 1