5. Neskutočná zápcha

Na našej diaľnici pravidelne vzniká hrozná zápcha. Výbor pre modernizáciu diaľníc sa rozhodol konečne s tým niečo robiť. Zavolali si rôznych školených expertov, aby im s tým poradili. Prvý odborník povedal, že treba spraviť kruhový objazd, všetci predsa vedia, že proti zápche pomáhajú. Druhý odborník povedal, že zápcha by sa vyriešila, keby ľudia namiesto osobných áut cestovali autobusom. Tretí odborník povedal, že v Japonsku majú špičkový turbointeligentný semafór, čo má vstavanú AIčku na reguláciu zápchy.

Keď sa odborníci večnosť nevedeli dohodnúť, koho spôsob je najlepší, výbor sa nakoniec rozhodol proste skombinovať všetky ich návrhy. Postavili obrovský kruháč a pri výjazde z neho namontovali japonský turbosemafór. Tento honosný výtvor nazvali prvou turbookružnou križovatkou. Ale stala sa osudná chyba. Zabudli, že v Japonsku sa jazdí po ľavej strane, takže semafór je naopak. Namiesto toho, aby púšťal autobusy z kruháča von, sú nútení ďalej krúžiť. Zápcha je tisíckrát horšia, ako predtým.

Úloha

Na turbookružnej križovatke stojí v rade pred semafórom \(n\) autobusov. Turbosemafór pomocou AIčky rozoznáva, koľko majú cestujúcich. Na každú zelenú pustí niekoľko autobusov, a to tak, aby počet ľudí neprekročil \(r\). Tie budú pokračovať v krúžení a zaradia sa naspäť na koniec radu v rovnakom poradí. Prvý autobus, ktorý by spôsobil že súčet stúpne nad \(r\), dostane červenú a musí čakať.

Ako špeciálny prípad, žiaden autobus nemôže prejsť viackrát počas tej istej zelenej. Aj keby bolo \(r\) dostatočne veľké, ak v rámci jednej zelenej semafór pustí všetky autobusy, prepne sa okamžite na červenú.

Cestujúcim ešte zostáva posledný kúsok nádeje. Po \(k\) zelených to turbosemafór nezvládne, prehreje sa mu grafická karta a exploduje. Potom budú môcť všetky autobusy konečne odísť.

Výbor by chcel odhadnúť, koľko ekonomickej škody a stratenej produktivity to celé spôsobilo. Preto potrebujú zistiť súčet, koľko ľudí prešlo križovatkou na každú zelenú až kým sa semafór nepokazil. S touto úlohou si však nevedia dať rady, preto pripadla ako obvykle vám.

Formát vstupu

Na prvom riadku vstupu sú tri medzerou oddelené čísla \(r, k, n\) \((1\leq r, k \leq 10^9, 1 \leq n \leq 10^6)\) kde \(r\) je maximálny počet ľudí čo môže prejsť na jednu zelenú, \(k\) je počet zelených, a \(n\) je počet čakajúcich autobusov.

Na nasledujúcom riadku je \(n\) medzerou oddelených čísel \(a_1,\dots,a_n\) \((1\leq a_i \leq r)\), \(i\)-te z nich popisuje počet ľudí v \(i\)-tom autobuse. Prvý autobus stojí na začiatku radu hneď pri semafóre, \(n\)-tý na konci.

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, počet ľudí, ktorí prejdú turbookružnou križovatkou.

Hodnotenie

Sú štyri sady testovacích vstupov. V jednotlivých sadách platia nasledujúce obmedzenia:

Pozor! Odpovede sa nemusia zmestiť do bežných celočíselných premenných. Preto odporúčame použiť napríklad premenné typu long long v c++.

Príklady

Input:

11 6 5
3 7 8 8 8

Output:

52

Na prvú zelenú semafór pustí prvý a druhý autobus (spolu 10 ľudí). Keď sa zaradia na koniec, nové poradie bude [8, 8, 8, 3, 7]. Na druhú zelenú prejde jeden autobus s 8 ľuďmi a na tretiu ďalší 8. V tomto momente to bude [8, 3, 7, 8, 8]. Na štvrtú zelenú prejdú autobusy 8 (čo bol pôvodne posledný) a 3 (pôvodne prvý). Na piatu zelenú prejde 7 a na šiestu 8. Spolu prejde \(10 + 8 + 8 + 11 + 7 + 8 = 52\) ľudí.

Input:

99 3 5
1 2 3 4 5

Output:

45

Na každú zelenú prejde všetkých 5 autobusov. Semafór by púšťal aj viac ľudí, ale už nemá koho.