The kids at DACT elementary school are very excited since they have their annual day coming up. On this occasion, the students get a chance to display all their projects and art work, as well as perform on stage for all the parents and other guests who will be coming. Since organizing an event so big requires a lot of effort, the poor teachers alone cannot handle it all. So, they decide to ask some of the students to volunteer to lend a hand.

You are the class teacher of one such kindergarten class with N students, and you need to select exactly k of your students for the volunteer group. Luckily for you, all the kids are very enthusiastic and excited and everyone wants to help out! But you also know that many of these students are very naughty and may start playing with each other halfway through instead of doing work. So you want to select this group of students in a smart manner to avoid such a scenario.

Since you have been their class teacher for nearly a year, you know beforehand how naughty each kid is, and have assigned "goodness" scores to each of the students accordingly. The higher the score for a student, the less naughty he/she is. You can also use this individual goodness score to calculate the score for a group of students as follows :

Goodness(a₁, a₂ ... a_n) = (|a₁|+|a₂| ... |a_n|) * (-1)^r

Where a₁, a₂... an are the goodness scores of the n students in that group, and r is the number of naughty students in that group. (Note: A naughty student is one with a negative goodness score)

Also |x| refers to the absolute value of x. (|x|=x if x>0. Else |x|=-x).

Given the goodness scores of all the students in your class, it is up to you to select exactly k students such that their group goodness score is maximum.

Input

The first line contains 2 space separated integers N and k. (1 <= k <= N <= 10⁵). Here N is the total number of students in your class, and k is the number of students to be selected.

This is followed by N space separated integers a₁, a₂ ... a_N, where a_i is the goodness score of the i^th student. (|a_i| <= 10⁹)

Output

On a single line output the maximum possible goodness value of any group of exactly k students that you may select.

Example

Input #1:
10 1
1 2 3 4 5 6 7 8 -9 9
 
Output #1:
9

Input #2:
10 3
1 2 3 4 5 6 7 -8 -9 9

Output #2:
26

Input #3:
3 3
12 78 2

Output #3:
92

Explanation

Input #1: Since you need to select exactly one student, you will select the one with the maximum individual goodness score, so the answer is 9.

Input #2: Here, the maximum score is obtained by selecting the students with scores of { -8, -9, 9 }, so the corresponding final value is: (|-8|+|-9|+|9|)*(-1)² = 26*1 = 26

Input #3: Here you have no choice but to select all the students. So the answer is 92.