kds

Se consideră un șir de numere naturale $a_1$, $a_2$, $\dots$, $a_n$ așezate circular. Acest lucru înseamnă că $a_1$ are ca vecini numerele $a_n$ și $a_2$, iar $a_n$ are ca vecini pe $a_{n-1}$ și $a_1$. Se consideră de asemenea un număr natural $K$.

Cerinţă

Să se determine suma maximă care se poate obține din exact $K$ secvențe nevide, disjuncte și ne-vecine.

Date de intrare

Fişierul kds.in conţine pe prima linie numerele naturale $n$ și $K$, iar pe linia a doua, separate prin câte un spațiu, numerele $a_1$, $a_2$, $\dots$, $a_n$.

Date de ieșire

Fişierul kds.out conţine un singur număr natural reprezentând suma maximă care se poate obține din $K$ secvențe nevide, disjuncte și ne-vecine.

Restricții și precizări

• $2 \leq 2 \cdot K \leq n \leq 10 \ 000$
• $1 \leq a_i \leq 10 \ 000$, $i = 1 \dots n$
• Două secvențe sunt disjuncte dacă nu au niciun element comun.
• Două secvențe sunt ne-vecine dacă sunt separate prin cel puțin un element care nu aparține nici uneia din cele două secvențe.

Exemplu

kds.in

7 2 
3 7 2 1 2 4 5

kds.out

20

Explicație

Cele două secvențe sunt $1$ și $4 \ 5 \ 3 \ 7$.

Atenție, nu se pot alege secvențele $3 \ 7 \ 2$ și $2 \ 4 \ 5$ pentru că ele sunt vecine ($5$ este vecin cu $3$).