스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Singapore Flyer © CEphoto, Uwe Aranas
Efter att ha följt en mycket väloptimerad rutt genom flygplatsen är det svenska laget äntligen framme vid IOI i Singapore. Under den första exkursionen får alla N lag på IOI åka i det jättestora pariserhjulet Singapore Flyer. Pariserhjulet har M stycken vagnar och det tar även M minuter för hjulet att snurra ett varv (det tar alltså 1 minut för varje vagn att flyttas ett steg).
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 (1 ≤ N,M ≤ 2 · 10^5), antalet lag och antalet vagnar i pariserhjulet.
Den andra raden innehåller N heltal T_1, …, T_N (1 ≤ T_i ≤ 10^9), där T_i är antalet som 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.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poängvärde | Gränser |
| 1 | 20 | 1 ≤ N, M, T_i ≤ 100 |
| 2 | 30 | 1 ≤ N, M, T_i ≤ 1000 |
| 3 | 25 | 1 ≤ N, M ≤ 1000 |
| 4 | 25 | Inga ytterligare begränsningar. |
Förklaring av exempelfall
(그림은 원문 저장소에서 볼 수 있습니다)
Figur 1: Exempelfall 1
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.
예제
예제 1
4 3 2 2 1 1
8
예제 2
1 4 2
8
예제 3
3 4 3 1 3
14