A2 - Hotely

Protiteroristická jednotka CTU (Counter-Terrorist Unit) na čele s Jackom Bauerom potrebuje vašu pomoc! Agenti CTU sa dozvedeli, že teroristi získali veľkú zásobu nebezpečnej výbušniny. Nemajú však dostatok agentov na to, aby pokryli všetky ohrozené mestá – potrebovali by preto program, ktorý pre každé mesto zráta, či sa naňho teroristom oplatí zaútočiť.

V jednom z monitorovaných miest stojí na hlavnom námestí v rade vedľa seba N hotelov. Výbušnina, ktorú teroristi získali, je dostatočne silná nato, aby okrem hotela, v ktorom je umiestnená, zničila ešte aj K susedných hotelov po obidvoch jeho stranách. Aby však nevzbudili podozrenie, musia si teroristi prenajať izbu v každom z hotelov, do ktorého chcú výbušninu umiestniť. Zistite, koľko najmenej musia teroristi zaplatiť za ubytovanie, ak chcú zničiť všetkých N hotelov.

Vstup

Prvý riadok vstupu obsahuje dve medzerou oddelené celé čísla N a K (0 ≤ K ≤ 10). Druhý riadok obsahuje N medzerou oddelených kladných celých čísel c_i – ceny za prenájom izby v jednotlivých hoteloch (1 ≤ c_i ≤ 1000).

Výstup

Výstupom má byť jediný riadok obsahujúci jedno celé číslo – najmenšiu možnú cenu, ktorú musia teroristi zaplatiť.

A1

1 ≤ N ≤ 20

A2

1 ≤ N ≤ 100 000

Príklad

Vstup:

6 2
20 30 15 10 30 30

Výstup:

25