БИЗНЕС

Sashka, the noisy doner seller from Korenyak, is walking along the main street of her hometown. She knows that the street has N doner shops, numbered 1 to N according to their position. She wants to establish a monopoly on the doner business, so she will buy every one of them. Sashka knows the price in leva at which she can get each doner shop: the owners of the i-th would sell it to her for exactly ai leva, where ai is an integer. Let the sale price of some doner shop be c. If c is positive, Sashka must spend c leva to buy it. Because of the increased price of electricity, some doner shops are willing to get rid of this business even at a loss. Then c is negative, and Sashka would receive |c| leva by becoming the owner of the doner shop. When c = 0, Sashka neither spends nor receives money, but she gets the doner shop. Thus the total amount of money needed to establish the monopoly is a1 + a2 + a3 + ⋯ + aN. She wants to make it as small as possible. For this purpose, she can talk to the owners of some doner shop p up to K times (she may not do it at all), and with her persuasion skills she will change their opinion about their doner shop, and accordingly the price at which they would sell it. Then, if the price of the p-th doner shop was x, the price after the conversation becomes −x, regardless of whether x is positive or negative. If x is 0, the price does not change. However, Sashka gets carried away, continues down the street, and has the same conversation with the p + 1, p + 2, p + 3, …, N doner shops, and they also change their minds. More formally, if she talks to the p-th doner shop (1 ≤ p ≤ N), then ap ∶= −ap, ap+1 ∶= −ap+1, …, aN ∶= −aN, where : = denotes assignment. For example, let a = {1, 4, 5, −2, 3} and Sashka talks to the owners of all doner shops from the third onward, then a = {1, 4, −5, 2, −3}. If after that she talks to all of them from the first onward, then a = {−1, −4, 5, −2, 3}. Sashka wants to know the minimum possible total price she could get after up to K conversations. Write a program price that answers her question.

The first line of the standard input contains two positive integers N and K. The next line contains N integers, where ai is the price of the i-th doner shop.

On one line of the standard output, print the minimum possible total price.

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