Запис пісень#810
Під час трансляції музичного концерту підприємець вирішив зайнятися бізнесом з виробництва касет. У нього є касет, кожна з яких має тривалість , і він прагне записати на них якомога більше пісень. Пісні (загальна кількість ) передаються в порядку 1, 2, \ldots, N і мають відомі тривалості L(1), L(2), \ldots, L(N). Підприємець може виконувати одну з наступних дій:
записати наступну пісню на касету (якщо вона туди поміщається) або пропустити її;
якщо пісня не поміщається на поточну касету, він може пропустити пісню або почати записувати її на нову касету. При цьому стара касета відкладається і більше не використовується.
Визначте максимальну кількість пісень, які підприємець може записати на касети.
Перший рядок містить число (M \leq 200).
Другий рядок — (D \leq 10^9).
Третій рядок — (N \leq 500).
Четвертий рядок — L(1), L(2), \ldots, L(N). Всі L(i) \leq D.
Всі вхідні параметри — натуральні числа.
Виведіть одне число — максимальну кількість пісень, яку можна записати.
Приклад 1