Se citesc n numere intregi si un numar natural K. Puteti alege, de exact K ori, un element al vectorului si sa ii schimbati semnul (aceeasi pozitie poate fi aleasa de mai multe ori). Determinati, folosind metoda Greedy, suma maxima posibila a vectorului dupa exact K astfel de operatii.
- Date de intrare
- Pe prima linie se citesc n si K. Pe a doua linie se citesc cele n numere.
- Date de iesire
- Se afiseaza un singur numar: suma maxima posibila.
- Restrictii
- 1 <= n <= 100000, 0 <= K <= 10^9, -1000 <= element <= 1000
Exemple
Exemplul 1
Intrare
3 1 -2 1 3
Iesire
6
Exemplul 2
Intrare
5 2 -1 -1 -1 -1 -1
Iesire
-1