5. Prechádzka lesom

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu arrays_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na [email protected]

Žaba je prepracovaný a tak sa na víkend vybral do lesa. Potuluje sa lesom, dýcha čerstvý vzduch, nachvíľu nemyslí na všetky povinnosti, ktoré má a užíva si vtáčí spev. V jednom momente však zbadá mláku, potom druhú, tretiu a štvrtú. Narazil na močiar a rád by sa z neho dostal s čo najmenším úsilím.

Poobzerá sa a hovorí si: “Tamtú mláku by som vedel obísť tadiaľ. Hmmm, ale veď som predsa Žaba! Mohol by som ju preto preskočiť a ušetriť dobrých \(60\) kilojoulov.”

“Ale tamtá sa mi preskočiť neoplatí, to by ma stálo viac energie ako to obísť.”

Keď sa Žaba vrátil domov, zaujímalo ho, ako veľa energie vyplytval. A keďže jemu sa to počítať nechce, nechal to na vás.

Úloha

Dostanete od nás niekoľko čísel, ktoré vyjadrujú množstvo energie, potrebnej na obídenie jednotlivých mlák. Ďalej od nás dostanete dĺžku skoku, vyjadrenú počtom mlák, ktoré Žaba jedným skokom preskočí. Ak sa totiž Žaba rozhodne skočiť, musí to byť poriadny skok cez niekoľko mlák. Takisto vám zadáme množstvo energie, čo ho takýto skok stojí.

Vašou úlohou je vypočítať, koľko najmenej energie bolo potrebnej na prejdenie celého močiaru.

Formát vstupu

Na prvom riadku sa nachádzajú tri čísla \(n\), \(d\), \(k\) (\(1 \leq n \leq 100\,000\), \(1 \leq d \leq n\), \(1 \leq k \leq 100\,000\)) – \(n\) označuje počet mlák, \(d\) je veľkosť Žabovho skoku a \(k\) je množstvo energie, ktoré ho jeden skok stojí. Hodnota \(d\) udáva počet mlák, ktoré preskočí jednným skokom.

Na druhom riadku je \(n\) čísiel – \(i\)-te označuje množstvo energie potrebného na obídenie \(i\)-tej mláky. Pre každé číslo \(x\) na tomto riadku platí: \(1 \leq x \leq 1\,000\).

Žabovu cestu si môžete predstaviť takto: Na začiatku sa Žaba nachádza pred prvou mlákou a musí prekráčať/doskákať až za poslednú. Kráčanie ho vždy posunie o jednu mláku ďalej, skok ho presunie ďalej o \(d\) mlák.

Pozor: Žaba svojim skokom nemôže skočiť ďalej ako priamo za poslednú mláku. Nevie totiž, aké nebezpečenstvo za močiarom môže číhať, kedže nemá túto oblasť zmapovanú.

Formát výstupu

Na výstup vypíšte jedno číslo, najmenšie množstvo energie, ktoré Žaba musel vydať aby sa úspešne dostal z močiaru. Môžete predpokladať, že toto číslo sa vám zmestí do bežnej celočíselnej premennej, akou je napríklad int v C++.

Hodnotenie

Vstupy sú rozdelené do troch sád, pre ktoré platia nasledovné obmedzenia:

Príklady

Input:

7 3 4
3 4 1 1 1 2 7

Output:

9

V tomto prípade Žaba najskôr zo začiatočnej pozície preskočí 3 mláky, ktorých obchádzanie by ho stálo \(3+4+1 = 8\) energie. Tento skok ho stojí 4 energie. Následne obíde štvrtú mláku, čo ho stojí 1 energiu. Nasleduje skok až za poslednú mláku. Vo výsledku teda minie \(4 + 1 + 4 = 9\) energie.

Input:

5 4 4
7 2 3 2 6

Output:

10

V tomto prípade sa najviac oplatí preskočiť prvé štyri mláky a poslednú prejsť pešo. Takéto riešeniu bude Žabu stáť \(4+6 = 10\) energie.

Všimnite si, že Žaba môže skákať iba spred prvej alebo spred druhej mláky. Ak by skákal neskôr, doskočil by mimo močiaru, čo spraviť nechce. Preto má iba tri možnosti ako močiarom prejsť – neskákať (\(7 + 2 + 3 + 2 + 6 = 20\)), skočiť spred prvej mláky (\(4 + 6 = 10\)) alebo skočiť spred druhej mláky (\(7 + 4 = 11\)).