VOLNTEER - Annual Day

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(a1, a2 ... an) = (|a1|+|a2| ... |an|) * (-1)r

Where a1, a2... 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 <= 105). 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 a1, a2 ... aN, where ai is the goodness score of the ith student. (|ai| <= 109)

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)2 = 26*1 = 26

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


Added by:Gowri Sundaram
Date:2013-03-09
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2019-07-06 12:32:15
With Python, 40 lines of code is an ugly, bloated solution and that's exactly my case.. Ifelsed my way to AC, no idea how to generalise and probably won't look back either, annoying kind of problem.
2016-07-19 10:00:55
running at the first 49 test and then got WA could anyone give me an advice :)
2016-06-11 19:51:13 shikhar0037
Don't categorise the problem in cases . Instead generalise the solution . 40 Line code AC in a go :)
2015-12-21 19:58:09 Goru
Running 40+ Judges then gives TLE :(
2015-05-28 22:11:06 Kshitij Agarwal
how many test cases are there in total for it?
2014-12-24 17:42:00 :(
Any tricky cases? My code seems to work fine but getting WA... :(
EDIT: Finally AC after 7WA... Good problem ;)

Last edit: 2014-12-28 05:22:30
2013-07-10 20:47:34 _maverick
be careful for the computation!! use long long @Rishabh Dugar . I believe u faced my problem,cases will be correct but for maximized sum use long long.I got AC by that.
2013-06-19 06:09:57 Rishabh Dugar
running(40)-n then gives me wa,,i have checked my code for the following as well;;
i/p
5 3
300 -250 50 200 -150
o/p
700
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.