В разгар дачного сезона на автобусной остановке собирается большая очередь. Редкий случай, когда человек едет на дачу один, обычно собирается целая компания, именно поэтому люди в очереди стоят группами.
В очереди на автобус стоят n групп людей. В i-й от начала очереди группе ai человек. Каждые 30 минут на остановку подъезжает пустой автобус, в который помещается не более m человек. Конечно, первыми в автобус проходят люди из первой группы, затем люди из второй группы и так далее. Обратите внимание, что люди в очереди ни при каких обстоятельствах не пропускают друг друга вперед. Более того, если какая-то группа не помещается целиком в текущий автобус, то она ждет следующего автобуса, как и все люди стоящие за этой группой в очереди.
Ваша задача — определить, сколько потребуется автобусов, чтобы перевезти все n групп в дачный поселок.
Выходные данные
Выведите единственное целое число — сколько потребуется автобусов, чтобы перевезти все n групп в дачный поселок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
2 3 2 1
|
3
|
|
2
|
3 4
1 2 1
|
1
|