Problema Salata de boeuf

Dorel urmează să își invite prietenii la el acasă cu prilejiul zilei sale de naștere. Grupul lui de prieteni, format din k + 1 prieteni (Dorel și cei k prieteni ai săi), adoră la nebunie salata de boeuf. Ne mai mirăm de ce? Salata de boeuf este gustoasă și se prepară ușor.

Din păcate, Dorel nu și-a dat seama cât de repede a trecut timpul și a realizat că prietenii lui urmează să vină foarte curând. Panicat și precipitat, dar în aceeași măsură delăsat, Dorel îți cere ajutorul tău în prepararea celor k salate de boeuf. Acesta are câteva reguli la care ține foarte mult și te roagă și pe tine să le respecți când prepari salatele.

Dorel are așezate în linie pe blatul din bucătăria sa n ingrediente pentru pregătirea salatelor: morcovi, cartofi, maioneză și multe altele. Pentru fiecare ingredient a notat un scor de nesănătate , pentru a se putea asigura că își ține prietenii la dietă. Salatele se prepară astfel: toate cele n ingrediente așezate în linie se împart în k secvențe de ingrediente consecutive, iar din fiecare secvență de ingrediente se prepară câte o salată pentru câte un prieten de al lui Dorel.

Acum, pentru a putea crea salate cât mai sănătoase, Dorel vrea ca salatele să fie împărțite în așa fel încât suma maximă a scorurilor de nesănătate ale unei secvențe să fie cât de mică posibil. Îl poți ajuta?

Cerință

Dându-se n, k și scorurile de nesănătate ale celor n ingrediente, să se determine, din împărțirea optimă a celor n ingrediente în k secvențe, care este maximul sumei a scorurilor de nesănătate ale secvențelor date.

Cu alte cuvinte: dându-se un șir de n valori, să se împartă întreg șirul în k secvențe astfel încât suma maximă a scorurilor de nesănătate ale secvențelor să fie cât de mică posibil.

Date de intrare

Fișierul de intrare salata.in conține pe prima linie numerele naturale n și k separate prin câte un spațiu. Pe a doua linie se află cele n scoruri de nesănătate ale ingredientelor în ordinea de pe blat. Scorurile sunt numere naturale separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire salata.out va conține un singur număr natural, reprezentând suma maximă a scorurilor unei secvențe dacă se face împărțirea optimă.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 100.000
• 1 ≤ scorurile de nesănătate ale ingredientelor ≤ 1.000.000.000
• Salatele trebuie să conțină cel puțin un ingredient
• Lui Dorel nu îi pasă de ce ingrediente se folosesc într-o salată (poate să fie o salată doar cu morcovi), atât timp cât este cât de sănătoasă posibil

Subtask 1 (10 puncte)

• n = k

Subtask 2 (20 de puncte)

• 1 ≤ k ≤ n ≤ 1000

Subtask 3 (70 de puncte)

• Fără alte restricții

Exemplu