Old Songs About the Main - 3
During the broadcast of the concert "Old Songs About the Main - 3," entrepreneur K decided to venture into the cassette production business. He has M cassettes, each with a capacity of D minutes, and aims to record as many songs as possible on them. There are N songs available, listed in sequence from 1 to 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. Once a cassette is set aside, no further songs can be recorded on it.
Your task is to determine the maximum number of songs that the entrepreneur can record on the cassettes.
Input
The first line contains the number M (M ≤ 100).
The second line contains D (D ≤ 300).
The third line contains N (N ≤ 300).
The fourth line lists the durations of the songs: L(1), L(2), ..., L(N). Each L(i) is less than or equal to D.
Output
Output a single number representing the maximum number of songs that can be recorded.