Problem G
Tomtens släde

Nu är det julafton och det är dags för tomten att dela ut alla julklappar! Det finns dock väldigt många julklappar att dela ut och tomtens julklappssäck rymmer bara $N$ liter. Alla julklappar från tomtens julklappsverkstad läggs i en av deras $M$ olika storlekar av lådor innan de slås in i julklappspapper. Storlek nummer $i$ rymmer $2^i$ liter, där $i$ är mellan $0$ och $M-1$. (Så om $N$ skulle vara $3$ har verkstaden lådor av storlekarna $1$, $2$ och $4$ liter.)

Hur många vändor måste tomten åka för att dela ut alla klappar?

Indata

Första raden indata består av två heltal, $N$ och $M$ ($1 \leq M \leq 30, N = 2^k$ för något heltal $k$ där $0 \leq k \leq 30$).

Därefter kommer $M$ rader med var sitt heltal där rad $i$ ($0 \leq i < M$) beskriver hur många julklappar av storlek $i$ tomten ska dela ut. Det är garanterat att ingen julklapp är större än storleken på tomtens julklappssäck.

Utdata

Skriv ut ett heltal, antalet vändor tomten måste åka för att dela ut alla julklappar.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I exempelfall $1$ rymmer tomtens julklappssäck $2$ liter och det finns bara en paketstorlek: $1$ liter. Tomten behöver alltså leverera de $1000$ paketen $2$ i taget vilket går på $1000/2=500$ vändor.

I exempelfall $2$ rymmer tomtens julklappssäck $4$ liter och det finns två paketstorlekar: $1$ och $2$ liter. Tomten kan leverera alla paket på 3 vändor här, till exempel genom att först åka en vända med de två tvåliterspaketen och sen två vändor med tre i taget av enliterspaketen.

2 1
1000

500

4 2
6
2

3

8 3
1
0
3

2

8 4
3
1000000000
4
1

250000004