BigMac

"Vrei să vezi o țeapă?" *iese din apel*

Cerință

Se dă $n, k$ și un șir $a$ de $n$ numere întregi. O operație de flip pe un număr din $a$ constă în schimbarea semnului numărului ($1$ devine $-1$, iar $-5$ devine $5$). Să se afle suma maximă a unei subsecvențe contigue din $a$ care nu conține numere negative, după ce se fac exact $k$ operații de flip, pe care voi le veți alege.

Date de intrare

Pe prima linie se găsesc două numere naturale, $n$ și $k$. Pe următoarea linie se găsesc $n$ numere întregi, elementele șirului $a$.

Dacă folosiți citire cu std::cin, vă recomandăm să adăugați aceste linii la începutul programului:

std::ios_base::sync_with_stdio(0);
std::cin.tie(0);

Date de ieșire

Pe prima linie se va găsi un singur număr natural, reprezentând răspunsul.

Restricții și precizări

• $0 \leq k \leq n \leq 1 \ 000 \ 000$.
• $-10^9 \leq a_i \leq 10^9$, pentru $i$ de la $1$ la $n$.
• Se pot face mai multe operații flip pe același număr.
• Se garantează că se pot face $k$ operații de flip astfel încat să existe cel puțin un număr pozitiv în $a$.

Exemplul 1

stdin

7 2
4 -2 -3 1 10 -1 5

stdout

20

Explicație

Facem flip la elementele de pe pozițiile $2$ și $3$. Șirul devine $4 \ 2 \ 3 \ 1 \ 10 \ -1 \ 5$. Suma maximă a unei secvențe care conține doar numere pozitive este $4 + 2 + 3 + 1 + 10 = 20$.

Exemplul 2

stdin

5 2
2 3 -1 4 6 

stdout

14

Explicație

Facem flip la elementele de pe pozițiile $1$ și $3$. Șirul devine $-2 \ 3 \ 1 \ 4 \ 6$. Suma maximă a unei secvențe care conține doar numere pozitive este $3 + 1 + 4 + 6 = 14$.