БИЗНЕС

코레냐크 슈멘카타 사슈카는 고향 마을의 중심가를 걷고 있다. 그녀는 거리에는 위치 순서대로 1번부터 N번까지 번호가 붙은 N개의 도네르 가게가 있다는 것을 알고 있다. 그녀는 도네르 사업의 독점을 세우고 싶어서, 그 가게들 전부를 사려고 한다. 사슈카는 각 도네르 가게를 살 수 있는 레바 단위의 가격을 알고 있다. i번째 가게의 주인은 정확히 ai 레바에 팔 것이며, ai는 정수이다. 어떤 도네르 가게의 판매 가격을 c라고 하자. c가 양수이면 사슈카는 그것을 사기 위해 c레바를 써야 한다. 전기 가격의 상승으로 인해 일부 도네르 가게는 손해를 보더라도 그 사업에서 벗어나려고 한다. 그러면 c는 음수이고, 사슈카는 그 도네르 가게의 주인이 되면서 |c|레바를 받는다. c = 0이면 사슈카는 돈을 쓰지도 받지도 않지만, 도네르 가게를 얻게 된다. 따라서 독점을 세우는 데 필요한 총 금액은 a1 + a2 + a3 + ⋯ + aN이다. 그녀는 이 금액을 가능한 한 작게 만들고 싶어 한다. 이를 위해 그녀는 최대 K번(전혀 하지 않아도 된다) 어떤 도네르 가게 p의 주인과 대화할 수 있고, 그녀의 설득 능력으로 그 가게에 대한 생각, 즉 팔 가격을 바꿀 수 있다. 그러면 p번째 도네르 가게의 가격이 x였을 때, 대화 후의 가격은 x가 양수인지 음수인지에 상관없이 −x가 된다. x가 0이면 가격은 바뀌지 않는다. 하지만 사슈카는 흥이 나서 거리를 계속 따라 내려가며 p + 1, p + 2, p + 3, …, N번째 도네르 가게와도 같은 대화를 하고, 그들도 생각을 바꾼다. 더 형식적으로 말하면, p번째 도네르 가게와 대화하면(1 ≤ p ≤ N), ap ∶= −ap, ap+1 ∶= −ap+1, …, aN ∶= −aN이고, 여기서 : =는 대입 기호이다. 예를 들어 a = {1, 4, 5, −2, 3}이고 사슈카가 세 번째부터의 모든 도네르 가게 주인과 대화하면, a = {1, 4, −5, 2, −3}이다. 그 후 첫 번째부터의 모든 가게와 대화하면, a = {−1, −4, 5, −2, 3}이다. 사슈카는 최대 K번의 대화 후에 얻을 수 있는 최소 가능한 총 가격이 얼마인지 알고 싶어 한다. 그녀의 질문에 답하는 프로그램 price를 작성하시오.

표준 입력의 첫 번째 줄에는 두 개의 양의 정수 N과 K가 주어진다. 다음 줄에는 N개의 정수가 있고, ai는 i번째 도네르 가게의 가격이다.

표준 출력의 한 줄에 최소 가능한 총 가격을 출력한다.

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