Cerința

Gug pregătește un festin pentru prietenii săi. Festinul constă în $N$ mâncăruri aranjate într-un rând. Mâncarea $i$ dă valoarea de satisfacție $A_i$ când este consumată. Cum unele mâncăruri pot fi expirate, ele pot avea valoarea de satisfacție $A_i$ negativă.

Există un total de $K$ persoane care participă la festin și fiecărei persoană îi va fi desemnată o secvență de mâncăruri pe care le poate consuma. Această secvență poate fi și vidă. Două secvențe nu se pot suprapune, fiindcă mâncarea nu poate fi consumată de mai multe ori. Gug dorește să aleagă secvențele de mâncăruri pentru fiecare persoană în așa fel încât valoarea totală de satisfacție să fie maximizată.

Date de intrare

Pe prima linie se vor afla numerele $N$ și $K$, cu semnificația din enunț.

Pe a doua linie se vor afla $N$ numere întregi, reprezentând elementele șirului.

Date de ieșire

Se va afișa suma maximă care se poate obține alegând maxim $K$ secvențe disjuncte.

Restricții și precizări

• Se recomandă folosirea fastio
• $1\le K\le N\le 3\cdot {10}^5$
• $0\le |A_i|\le {10}^9$

Subtask-uri

Exemplu 1:

Intrare

6 1
1 -2 3 -1 5 -6

Ieșire

7

Explicație

Soluția optimă este să alegem secvența $[3,-1,5]$, obținând astfel suma $7$.

Exemplu 2:

Intrare

6 2
1 2 3 -10 5 6

Ieșire

17

Explicație

Soluția optimă este să alegem secvențele $[1,2,3]$ și $[5,6]$, obținând astfel suma $17$.

Exemplu 3:

Intrare

6 4
-1 -2 -1 0 -5 -1

Ieșire

0

Explicație

Fiindcă toate secvențele au sumă non-pozitivă, este optim să nu alegem nicio secvență, obținând astfel suma $0$.