Problem E
Pariserhjulet

Singapore Flyer
© CEphoto, Uwe Aranas

Vissa lag verkar vara mer intresserade av att åka pariserhjul än andra, och därför får varje lag bestämma exakt hur många varv de vill åka. Det blir tråkigt för deltagarna om de måste gå av och sedan på igen innan de har åkt alla sina varv. Det har därför bestämts att när ett lag väl har satt sig i en vagn, så får detta lag sitta kvar i vagnen fram till att de har åkt alla sina varv. Detta betyder att om hjulet snurrar så att en vagn kommer ner till ingången, men det redan sitter ett lag i vagnen som vill fortsätta åka, så kan nästa lag inte gå in i vagnen. Detta lag måste då vänta på en tom vagn eller en vagn med ett lag som går av.

Lagen är väldigt effektiva på att gå in och ut ur vagnarna, så det tar ingen extra tid att byta lag i den nedersta vagnen.

Alla lag står just nu i kö framför pariserhjulet, och det svenska laget undrar hur lång tid det kommer ta innan alla har åkt.

Indata

Den första raden innehåller heltalen $N$ och $M$ separerade med blanksteg, antalet lag och antalet vagnar i pariserhjulet. Den andra raden innehåller $N$ heltal $T_1 ... T_ N$ separerade med blanksteg, där $T_ i$ är antalet varv lag nummer $i$ vill åka. Lagen är ordnade efter köplats, där $T_1$ är det första laget i kön.

Utdata

Skriv ut en rad med ett heltal, antalet minuter det kommer ta för alla lag att åka.

Begränsningar

Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda inskickning.

Förklaring av exempelfall

I exempelfall 1 finns det 4 lag och 3 vagnar. Lagen, som i bilden är Sverige, Norge, Finland och Danmark, vill åka 2, 2, 1 och 1 varv respektive. Notera att det danska laget inte kan gå in i pariserhjulet vid $t=3$ eller $t=4$ eftersom det svenska / norska laget redan sitter i den nedersta vagnen och vill i båda fallen åka ett varv till.

4 3
2 2 1 1

8

1 4
2

8

3 4
3 1 3

14