시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

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 n 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ż k 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 k razy. Dla uproszczenia zakładamy, że samoloty kursują w nocy.

입력

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

출력

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

예제 입력 1

5 2
7 -3 4 -9 5

예제 출력 1

13