Old Songs About the Main - 4
During the broadcast of the concert "Old Songs About the Main - 4," entrepreneur K decided to venture into producing cassettes. He has M cassettes, each with a playback capacity of D minutes, and aims to record as many songs as possible on them. There are N songs available, transmitted in the order 1, 2, ..., N, each with a known duration: L(1), L(2), ..., L(N). The entrepreneur can choose from the following actions:
Record the next song on the current cassette if it fits, or skip it;
If the song does not fit on the current cassette, he can either skip the song or start recording it on a new cassette. In this case, the previous cassette is set aside and cannot be used further.
Determine the maximum number of songs the entrepreneur can record on the cassettes.
Input
The first line contains the number M (M ≤ 200).
The second line contains D (D ≤ 10^9).
The third line contains N (N ≤ 500).
The fourth line contains L(1), L(2), ..., L(N). Each L(i) ≤ D.
All input parameters are natural numbers.
Output
Output a single number representing the maximum number of songs that can be recorded.