Se consideră un șir de numere naturale a[1], a[2], …, 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ța

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 de intrare 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], …, a[n].

Date de ieșire

Fișierul de ieșire kds.out va 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 ≤ 2*K ≤ n ≤ 10000
• 1 ≤ a[i] ≤ 10000, i=1..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).