eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Старые песни о главном - 4

Старые песни о главном - 4

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Во время трансляции концерта "Старые песни о главном - 4" предприниматель K. решил сделать бизнес на производстве кассет. Он имеет M кассет с длительностью звучания D каждая и хочет записать на них максимальное число песен. Эти песни (их общее количество N) передаются в порядке 1, 2, ..., N и имеют заранее известные длительности звучания L(1), L(2), ..., L(n). Предприниматель может выполнять одно из следующих действий:

  • записать очередную песню на кассету (если она туда помещается) или пропустить её;

  • если песня на кассету не помещается, то можно пропустить песню или начать записывать её на новую кассету. При этом старая кассета откладывается и туда уже ничего не может быть записано.

Определить максимальное количество песен, которые предприниматель может записать на кассеты.

Входные данные

Первая строка содержит число M (M200).

Вторая строка - D (D10^9).

Третья строка - N (N500).

Четвёртая строка - L(1), L(2), ..., L(n). Все L(i) ≤ D.

Все входные параметры натуральные числа.

Выходные данные

Необходимо вывести единственное число - искомое количество песен.

Пример

Входные данные #1
2
10
4
6 6 6 4
Выходные данные #1
3