Köpa tavlor

/problems/kopatavlor/file/statement/sv/img-0001.jpg
cc by-s
Mona har just flyttat och ska nu börja inreda. Hon har kommit fram till att hon behöver precis $k$ stycken tavlor, och har åkt till konstmarknaden för att handla. Mona är väldigt rik, och bryr sig inte alls om hur mycket tavlorna kostar, utan vill istället bara bli färdig så snabbt som möjligt.

På marknaden säljs $N$ tavlor längs en lång gata. Tavla $i$ tar $t_ i$ sekunder att köpa. Att gå från en tavla till nästa tar 1 sekund. Mona tar bussen dit och hem, så hon kan välja vid vilken tavla hon börjar och slutar. Vad är den kortaste tiden Mona kan köpa $k$ tavlor på?

Indata

Den första raden innehåller två heltal: $N$ ($1 \le N \le 2000$), antalet tavlor på marknaden, och $k$ ($1 \le k \le N$), antal tavlor Mona behöver köpa.

Den andra raden innehåller $N$ heltal: $1 \le t_1,t_2,...t_ n \le 1000$, antal sekunder det tar att köpa respektive tavla.

Utdata

Skriv ut ett heltal – det minsta antalet sekunder det kan ta för Mona att köpa $k$ tavlor.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$7$

$k=1$

$2$

$10$

$k=2$

$3$

$30$

$N \le 200$

$4$

$53$

Inga ytterligare begränsningar.

Exempelfall

Sample Input 1 Sample Output 1
4 2
3 3 5 1
6
Sample Input 2 Sample Output 2
6 4
7 4 3 10 2 5
18
Sample Input 3 Sample Output 3
10 5
4 7 2 1 8 6 7 2 1 10
18