Prihlásenie Registrácia  

C - Kolotoč

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Strýko Paul vlastní zábavný park, ktorého súčasťou je aj známe ruské kolo. Ktosi strýkovi poradil, aby omaľoval kabínky kolotoča rôznymi farbami. Časom sa však ukázalo, že nie každá farba u návštevníkov vyvoláva rovnaké emócie. O niektoré kabínky tak začal byť väčší a o iné menší záujem. V snahe vyrovnať tieto rozdiely preto strýko Paul určil vstupné pre každú kabínku zvlášť.

N kamarátov sa vybralo do strýkovho zábavného parku. Aj oni by sa chceli povoziť na už spomínanom ruskom kole. Ako správna partia chcú všetci bezpodmienečne sedieť buď v jednej alebo v niekoľkých po sebe idúcich susedných kabínkach. A potom, ako správny žrgloši, by chceli zaplatiť na vstupnom čo najmenej.

Úloha

Daný je počet kamarátov N, kapacita jednej kabínky kolotoča K, počet kabínok M a ceny vstupného za rezerváciu každej z kabínok (nie je možné si kupovať miesta v kabínke, iba rezervovať celú). Určte minimálne vstupné pre našich N kamarátov.

Vstup

Vstup bude v prvom riadku obsahovať kladné celé čísla N K M oddelené medzerou. (1≤M≤100 000),(1≤K≤100),(1≤N≤K.M).
Druhý riadok vstupu obsahuje ceny za jednotlivé kabínky (M kladných celých čísel oddelených medzerou). Žiadne z týchto čísel nie je väčšie ako 10 000.

Výstup

Výstupom má byť jediný riadok určujúci minimálne vstupné pre našich žrglošov.

Príklad

Vstup

7 2 10
80 70 40 90 100 60 70 80 80 50

Výstup

240
Poznámka: Potrebujeme kúpiť 4 kabínky. Najlacnejšou voľbou je kúpiť poslednú a prvé tri.