Tanie linie [A]

Limit pamięci: 256 MB

Bajtazar wybiera się na długo oczekiwany urlop, który ma zamiar spędzić, wygrzewając się na złotych piaskach plaż Morza Bitockiego. Biorąc pod uwagę swój biorytm, prognozę pogody i ofertę kulturalno-oświatową Bitocji, Bajtazar wyznaczył dla każdego z dni urlopu jego współczynnik rekreacji, który oznacza, jak dobrze w danym dniu Bajtazar będzie się bawił. Każdy ze współczynników jest liczbą całkowitą; być może ujemną - to oznacza, że Bajtazar w tym dniu wolałby być w domu i pielić ogródek.

Na szczęście Bajtazar nie musi spędzić całego urlopu nad morzem. Jego ulubione tanie linie lotnicze przygotowały promocję, dzięki której Bajtazar może zakupić aż biletów lotniczych po wyjątkowo atrakcyjnej cenie (każdy bilet jest na podróż nad Morze Bitockie i z powrotem).

Pomóż Bajtazarowi zaplanować urlop tak, by suma współczynników rekreacji dni, które spędzi on nad morzem, była jak największa, przy założeniu, że podczas urlopu może on polecieć nad morze co najwyżej razy. Dla uproszczenia zakładamy, że samoloty kursują w nocy.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (). W drugim wierszu znajduje się liczb (co do modułu nie większych niż ), które opisują współczynniki rekreacji kolejnych dni urlopu Bajtazara.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, która oznacza sumę współczynników rekreacji w optymalnym planie urlopu.

Przykład

Dla danych wejściowych:

5 2
7 -3 4 -9 5

poprawną odpowiedzią jest:

13

Autorzy zadania: Tomasz Idziaszek, Jakub Łącki.