Zadanie

Hra s nabíjacím traktorom

Počet bodov: 50

Združenie Energeticky Nenáročných Inovatívnych Traktorov (ZENIT) prinieslo na trh elektrický traktor. Priniesli hračkársku verziu aj na Každoročné Stretnutie Poľnohospodárov (KSP). Tí ju potom darovali Korešpondečnému Semináru z Programovania, ktorí s ňou vymysleli sústredkovú hru. O tejto sústredkovej hre je táto úloha.

Hra spočívala v tom, že na ceste bol položený hračkársky traktor na ručné nabíjanie. Postupne k nemu dobehli členovia tímu, zdvihli ho, v časovom limite pokrútili kľukou na nabíjanie a položili ho naspäť na cestu. Keď sa pri traktore vystriedali všetci z tímu, prišli vedúci, pustili traktor a odmerali, ako ďaleko hore kopcom vedel traktor prejsť.

Ako prezieravý člen sústredka vieš o každom účastníkovi povedať, ako veľmi vie za pridelený čas nabiť traktor. Taktiež vieš predpovedať, či je daný účastník nešikovný. Nešikovní účastníci položia traktor na cestu otočený naopak (a traktor po spustení pôjde do opačného smeru, ako by šiel predtým, než ho daný účastník nabíjal).

Vyber si z účastníkov \(K\)-členný tím tak, aby váš traktor prešiel čo najďalej hore kopcom.

Vstup a výstup

V prvom riadku vstupu sú dve čísla \(N\) a \(K\) - počet účastníkov a počet ľudí v tíme.

V druhom riadku je \(N\) celých čísel \(u_i\) popisujúcich účastníkov. Účastník \(i\) nabije traktor tak, že prejde o \(|u_i|\) milimetrov viac. Ak je \(u_i\) záporné, účastník je nešikovný a traktor otočí.

Traktor začína otočený smerom hore kopcom.

Formálne, ak vyberieme účastníkov s hodnotami \(a_1, \cdots, a_K\), pričom \(M\) z nich je záporných, traktor prejde \((|a_1|+\cdots+|a_k|) \cdot (-1)^M\) milimetrov hore kopcom.

Vypíšte najväčšie číslo \(v\) také, že sa dá vybrať \(K\) účastníkov, ktorí nabijú a otočia traktor tak, aby prešiel \(v\) milimetrov hore kopcom.

Vo vstupoch platí \(1 \leq K \leq N \leq 300\,000\) a \(1 \leq |u_i| \leq 10^9\).

Navyše, v prvej sade vstupov platí \(1 \leq N \leq 15\), v druhej \(K \leq 2\), a v tretej \(K \leq 5\). Vo zvyšných dvoch sadách neplatia obmedzenia navyše.

Príklady

Input:

5 3
5 -1 -6 7 -9

Output:

22

Ak vyberieme posledných troch účastníkov, tí nabijú traktor tak, že prejde |-6|+|7|+|-9| = 22 milimetrov. Tretí a posledný účastník traktor otočia, takže ostane smerovať hore kopcom.

Input:

5 3
5 -1 6 7 -9

Output:

18

Teraz je najlepšie zobrať do tímu prvého, tretieho a štvrtého účastníka. Najviac by nám traktor nabil piaty, ale ten je nešikovný a traktor by otočil dolu kopcom. Ak by sme zobrali aj druhého účastníka, traktor by skončil otočený hore kopcom, ale druhý účastník je slabý a neoplatí sa nám to.