4. Eeh?! Traktor na diaľnici?!

Cestár Jožo čoskoro ukončí svoju kariéru profesionálneho držiaka lopaty, a tak sa rozhodol, že vo svoj posledný deň spraví niečo také veľké, že to až samotný Pán Minister očuje. Zobral teda svoj traktor, pripojil naň orač a hybal poorať diaľnicu – však jak inako by spravil veľký kus roboty? Avšak, keď už bol na nájazde, tak sa zbadal, že diaľnicu treba poorať strategicky. Veď nový orač je drahý a nemôže zničiť ten jediný čo má pred tým, ako dokončí svoje veľdielo. Rozhodol sa teda, že si vyberie iba \(K\) úsekov, ktorým sa povenuje – t.j. tých \(K\) úsekov poriadne poorie a zvyšok popoludia strávi vo svojom obľúbenom šenku. Však i tak sa o ňom určite na titulkách bude písať.

Úloha

Na vstupe dostanete počet úsekov diaľnice. Každý úsek má kvalitu, ktorá je reprezentovaná nejakým prirodzeným číslom. Skupina po sebe idúcich úsekov \(u_1, u_2, \ldots, u_N\) má skupinovú kvalitu rovnú súčtu súčinov všetkých dvojíc v danej skupine. Napríklad, ak by sme mali len jeden úsek, tak ten má skupinovú kvalitu rovnú \(0\), keďže nemá s žiaden úsek do dvojice. Skupina dvoch úsekov má zas skupinovú kvalitu rovnú \(u_1u_2\) a trojica úsekov má skupinovú kvalitu rovnú \(u_1u_2 + u_1u_3 + u_2u_3\).

Ako už bolo spomínané, tak Jožo sa môže venovať len niektorým úsekom. Vždy, keď sa povenuje nejakému úseku s indexom \(i\), tak rozdelí skupinu úsekov \(u_1, \ldots, u_N\) na dve menšie skupiny \(u_1, \ldots, u_i\) a \(u_{i+1}, \ldots, u_N\), pričom týmto skupinám sa potom ráta skupinovú kvalita samostatne. Celková kvalita je teda súčet skupinových kvalít všetkých skupín.

Pomôžte Jožovi zistiť, akú najnižšiu celkovú kvalitu môže dosiahnuť, nech vyrobí naozaj veľký kus práce.

Formát vstupu

Na prvom riadku vstupu je jedno číslo \(N, 1 \leq N \leq 500\) – počet úsekov. Na druhom riadku je \(K, 1 \leq K \leq N\) – počet úsekov, ktorým sa môže Jožo povenovať. Na treťom riadku je \(N\) medzerou oddelených prirodzených čísel v rozsahu od \(1\) po \(100\).

Formát výstupu

Vypíšte jedno celé číslo – najmenšiu celkovú kvalitu, ktorú vie Jožo dosiahnuť.

Príklady

Input:

5
1
6 8 2 7 2

Output:

80

Najvýhodnejšie je povenovať sa úseku s kvalitou \(8\), potom dostaneme skupiny \((6,8)\), \((2,7,2)\) ktoré majú súčet skupinových kvalít rovný \((6\cdot 8) + (2\cdot 7 + 2\cdot 2 + 7\cdot 2) = 48+32 = 80\)

Input:

5
2
6 8 2 7 2

Output:

30

Jožo vyrobí skupiny \((6)\), \((8,2)\), \((7,2)\)