HONI 4. kolo 2019/2020 - 2. zadatak

Početkom ove godine američka tvrtka Amazon pokreće projekt Amazon Prime Air. To znači da ćete moći naručiti paket s Amazona, a njega će vam dostaviti dron u roku od 30 minuta.

Svaki dron u skladištu ima u redu svojih M paketa koje mora dostaviti tim redoslijedom kako su poredani. Za svaki paket znamo njegovu masu Ki , izraženu u kilogramima.

Dron u jednoj dostavi može prenijeti najviše N kilograma paketa i može ponijeti više uzastopnih paketa odjednom (počevši od prvog u redu). Naravno, zbroj kilograma ponesenih uzastopnih paketa mora biti manji ili jednak N. Amazon želi optimizirati broj polijetanja te ih zanima u koliko najmanje polijetanja dron može prenijeti pakete na zadana odredišta. Nažalost, oni to ne znaju izračunati pa su zamolili vas da to učinite umjesto njih.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 100) iz teksta zadatka.

U drugom je retku prirodan broj M (1 ≤ M ≤ 100) iz teksta zadatka.

U sljedećih M redaka nalazi se po jedan broj Ki (1 ≤ Ki ≤ N) koji označava masu i-tog paketa

Izlazni podaci

Ispišite minimalan broj polijetanja drona.

Primjeri test podataka

Ulaz

10
3
3
4
2

Izlaz

1

Ulaz

10
3
4
4
4

Izlaz

2

Ulaz

10
3
6
1
7

Izlaz

2

Objašnjenje

Optimalno je uzeti prvi paket u prvoj dostavi, a drugi i treći paket u drugoj dostavi.