Dirijor

Dirijorii mereu călătoresc dintr-o parte într-alta a lumii, trebuind să viziteze multe săli de concert. În particular, marele dirijor Scuțescu se află în tărâmul Eufoniei și trebuie să dirijeze mai multe concerte.

Tărâmul este liniar, fiind o înșiruire de $N + 1$ orașe, unde fiecare drum intre două orașe adiacente are câte un preț (în mărci eufonice) pentru bilete de autobuz. Vom nota cu $A_i$ prețul biletului pe care trebuie să îl plătească dirijorul pentru a se deplasa de la orașul $i$ la $i + 1$ sau invers.

Dirijorul se află inițial în orașul $1$ și urmează să susțină $P$ concerte. Fiindcă îi place să călătorească dintr-un capăt în altul al lumii, și-a stabilit toate concertele în orașele $1$ și $N + 1$ astfel: primul concert se află în orașul $N + 1$, al doilea concert se află în orașul $1$, al treilea concert se află în orașul $N + 1$, al patrulea concert se află în orașul $1$ și așa mai departe. Concertele trebuie susținute în ordine.

Pentru fiecare drum de la $1$ la $N + 1$ sau viceversa, se face o escală (adică de la $1$ la $x$ la $N + 1$ sau de la $N + 1$ la $x$ la $1$, unde $1 < x < N + 1$). Prețul unei escale este prețul maxim dintre toate biletele de autobuz folosite în acel drum care nu au fost cumpărate încă. Cu alte cuvinte, pentru o escală, se plătește valoarea maximă din subsecvența parcursă și acea valoare maximă e înlocuită cu $0$, iar atunci când dirijorul face un drum de la orașul din care pleacă înspre escală, sau de la escală până în orașul în care trebuie să susțină un concert, acesta nu are voie să meargă pe gratis.

De exemplu, pentru șirul $A$ de costuri $2, 5, 6, 3, 4, 9, 12, 7$, dacă am face o escală în orașul $4$, ar trebui să plătim $\max(2, 5, 6) + \max(3, 4, 9, 12, 7)$, adică 18 mărci eufonice, iar șirul se va transforma în $2, 5, 0, 3, 4, 9, 0, 7$.

Cerință

Să se determine costul minim pe care îl poate plăti dirijorul pentru a susține toate cele $P$ concerte.

Date de intrare

Pe prima linie se află numerele $N$ și $P$. Pe a doua linie se află $N$ numere naturale, reprezentând elementele șirului $A$.

Date de ieșire

Se va afișa costul minim pe care dirijorul trebuie să îl plătească pentru a-și face călătoria.

Restricții și precizări

• $1 \leq 2 \cdot P \leq N \leq 5 \ 000$
• $\sum_{i = 1}^{i \leq N} A_i \leq 2 \ 000 \ 000 \ 000$
• Toate valorile din $A$ sunt distincte.

Subtask 1 (6 puncte)

• $1 \leq N \leq 15$

Subtask 2 (9 puncte)

• $1 \leq N \leq 250$, $1 \leq P \leq 15$

Subtask 3 (17 puncte)

• $1 \leq N \leq 250$

Subtask 4 (17 puncte)

• $1 \leq N \leq 3 \ 000$

Subtask 5 (51 puncte)

• Fără restricții suplimentare

Exemplu

stdin

9 4
4 5 8 6 3 2 7 1 9

stdout

41