ЗАДАЧА B

Подарки к Новому году

Имя входного файла:presents.in
Имя выходного файла:presents.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

Все дети любят получать подарки к Новому году. Зная это, Дед Мороз со Снегурочкой заготовили большое количество подарков и запаковали их в ящики. Ящики получились различного веса. Для того, чтобы доставить из Лапландии в Харьков подарки, нужно погрузить их на оленьи упряжки. Известно, что одна оленья упряжка не может перевезти больше, чем N кг груза.

Чтобы не перепутать подарки, Дед Мороз пронумеровал все ящики и решил отправлять их строго в порядке номеров, т.е. сначала грузят 1-й ящик, затем 2-й и т.д. Вес каждого ящика не превосходит N кг. Если при погрузке очередного ящика на упряжку оказывается, что суммарный вес погруженных ящиков больше, чем N, то этот ящик грузят на новую упряжку. Чтобы не задерживать доставку подарков, загруженную упряжку сразу же отправляют в путь.

Напишите программу, которая сможет определить, сколько оленьих упряжек понадобится Деду Морозу, чтобы доставить все подарки харьковским детям.

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


Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – грузоподъемность оленьей упряжки. Вторая строка содержит натуральное число M (1 ≤ M ≤ 100) – количество ящиков. Третья строка содержит M натуральных чисел от 1 до N включительно – вес каждого ящика.

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


В выходной файл следует вывести единственное число – количество оленьих упряжек.

Пример


presents.in presents.out Примечание
10
5
2 4 3 4 3
2
На первую упряжку нужно погрузить первые три ящика (общий вес 9кг), а на вторую – оставшиеся два (общий вес 7кг)
100
4
20 20 20 40
1
Все ящики можно погрузить на одну упряжку
50
6
1 50 1 1 1 1
3
Первый ящик грузится на первую упряжку, второй ящик нужно грузить на вторую упряжку, так как его вес совпадает с грузоподъемностью упряжки, а оставшиеся четыре ящика грузятся на третью упряжку.