24289번 - БИЗНЕС 다국어

Кореняк шуменката Сашка се разхожда по главната в родния ѝ град. Тя знае, че по улицата има N дюнерджийници, номерирани с числата от 1 до N спрямо позицията им. Tя иска да установи монопол на дюнерджийския бизнес, заради това тя ще купи всяка една от тях. Сашка знае цената в левове, за която може да се сдобие с всяка една дюнерджийница – собствениците на i-тата биха я продали за точно a_i лева, като a_i е цяло число. Нека цената за продажба на някоя дюнерджийница е c. Ако c е положително, то Сашка трябва да изхарчи c лева, за да я купи. В следствие на повишената цена на тока, някои дюнерджии са склонни да се отърват от този бизнес, дори на загуба. Тогава c е отрицателно, а Сашка би получила |c| лева, като стане собственичка на дюнерджийницата. При c = 0, Сашка няма да изхарчи или получи пари, но ще получи дюнерджийницата. Така общата сума пари, нужна за установяване на монопола, е a₁ + a₂ + a₃ + ⋯ + a_N. Тя иска да я направи колкото се може по-малка. За тази цел, тя може до K пъти (може и въобще да не го прави) да разговаря със собствениците на някоя дюнерджийница p и с уменията си да убеждава, тя ще промени мнението за дюнерджийницата им, съответно и цената, за която биха я продали. Тогава, ако цената на p- тата дюнерджийница е била x, то цената след разговора би станала равна на −x, независимо от това дали x е положително или отрицателно. Ако x е равно на 0, цената не се променя. Сашка обаче се увлича, продължава надолу по улицата и води същия разговор с p + 1, p + 2, p + 3, … , N дюнерджийници, като и те си променят мнението. По-формално казано, ако разговаря с p-тата дюнерджийница (1 ≤ p ≤ N), то a_p ∶= −a_p, a_p+1 ∶= −a_p+1, … , a_N ∶= −a_N, като с : = е означен знак за присвояване. Например, нека a = {1, 4, 5, −2, 3} и Сашка разговаря със собствениците на всички дюнерджийници от третата нататък, то a = {1, 4, −5, 2, −3}. Ако пък след това разговаря с всички от първата нататък, то a = {−1, −4, 5, −2, 3}. Сашка иска да знае каква е минималната възможна обща цена, която би могла да получи, след проведени до K разговора. Напишете програма price, която отговаря на въпроса ѝ.

От първия ред на стандартния вход сe въвеждат две цели, положителни числа N и K. На следващия ред са разположени N цели числа, като a_i е цената на i-тата дюнерджийница.

На един ред на стандартния изход се извежда минималната възможна обща цена.

• 1 ≤ N ≤ 500 000 (И все пак те не са достатъчни да утолят глада на всички!)
• 1 ≤ K ≤ 100
• 0 ≤ |a_i| ≤ 10⁹