Zadanie

Hanebné praktiky

Počet bodov: 65

Do našej dediny zavíta zahraničná návšteva. Peniaze z eurofondov sme použili na kadečo, len nie na modernizáciu. Celá dedina tak dala hlavy dokopy. Ako len poukázať na obrovský ekonomický a kultúrny rast? Inšpirácia prišla rýchlo v podobe praktík Grigorija Alexandroviča Poťomkina a jeho falošných prenosných dedín. Rozhodli sme sa spoločne vystavať niekoľko budov (ehm, kulís) a tým na jednej strane poukázať na nové stavby, ale na druhej zakryť realitu za nimi. Budovy budeme stavať okolo cesty, po ktorej bude návšteva prichádzať a radi by sme z výhľadu na dedinu zakryli čo najviac. Zdroje, čas aj miesta na stavbu sú obmedzené, pomôžete nám toho pozakrývať čo najviac?

Úloha

Máme \(N\) miest vhodných na výstavbu, očíslovaných od \(1\) až po \(N\). Každé miesto má určený limit \(a_i\) tak, ako maximálne vysoká môže byť budova, ktorá na ňom stojí. Chceme postaviť maximálne \(k\) budov, aby sme nepôsobili podozrivo. Každá budova môže zaberať aj viac stavebných miest, avšak maximálne \(t\). Túto konštantu sme obdržali od estetikov, ktorí nám povedali, že dlhšia budova by už bola nevkusná. Budovy naviac musia pôsobiť esteticky, a tak nechceme, aby mala jedna budova na rôznych miestach rozdielnu výšku. Nájdite najväčšiu možnú plochu výhľadu, ktorú takto vieme budovami zakryť. Plochu, ktorú budova zakrýva pritom vypočítame ako súčin jej dĺžky a výšky.

Vstup a Výstup

V prvom riadku vstupu sú tri čísla \(N\), \(K\) a \(T\) - počet stavebných miest, maximálny počet budov, ktoré chceme postaviť a maximálna dĺžka budovy.

V nasledujúcom riadku sa nachádza \(N\) čísel \(a_1, a_2,\ldots , a_n\) - označujúcich maximálnu výšku budovy na danom stavebnom mieste.

Vypíšte najväčšiu možnú plochu, ktorú vedia novopostavené budovy zabrať, ak stavanie bude dodržiavať všetky spomínané obmedzenia.

Platí \(1 \leq N \leq 300\), \(1 \leq K \leq N\), \(1 \leq T \leq N\). Pre obmedzenia výšok budov na jednotlivých miestach platí \(1 \leq a_i \leq 300\).

Riešenie bude otestované na troch testovacích sadách. Pre prvú okrem vyššie spomenutých obmedzení naviac platí, že \(1 \leq N \leq 10\). Pre druhú zas, že \(1 \leq N \leq 100\).

Príklad

Input:

7 3 4
8 4 5 6 3 3 7

Output:

29

Postavíme 3 budovy. Prvá sa bude týčiť na prvom stavebnom mieste do výšky 8, druhá bude stáť na druhom až štvrtom políčku a jej výška bude 4. Posledná budova bude stáť na políčkach päť až sedem s výškou 3. Celkovo teda 3 budovy zaberú 1x8+3x4+3x3 = 29 jednotiek plochy.

Input:

7 3 5
8 4 5 6 3 3 7

Output:

30

Podobný príklad; dovolili sme ale dlhšie budovy (až dĺžky 5). Teraz sa nám oplatí postaviť budovy na prvom a poslednom políčku (obe dĺžky 1), a potom jednu dlhú budovu výšky iba 3 a dĺžky 5, a to od druhého až po predposledné políčko..