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.