VOLNTEER  Annual Day
Problem Statement
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_{1}, a_{2}.... a_{n} ) = ( a_{1}+a_{2}....a_{n} ) * (1)^{r}
Where a_{1}, a_{2}... 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^{5} ). 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_{1}, a_{2}... a_{N}, where a_{i} is the goodness score of the i^{th} student. ( a_{i} <= 10^{9 })
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:
92Explanation :
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 }.
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.
hide comments
nadstratosfer:
20190706 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. 

saloom:
20160719 10:00:55
running at the first 49 test and then got WA could anyone give me an advice :)


shikhar0037:
20160611 19:51:13
Don't categorise the problem in cases . Instead generalise the solution . 40 Line code AC in a go :) 

Goru:
20151221 19:58:09
Running 40+ Judges then gives TLE :( 

Kshitij Agarwal:
20150528 22:11:06
how many test cases are there in total for it?


:(:
20141224 17:42:00
Any tricky cases? My code seems to work fine but getting WA... :(


_maverick:
20130710 20:47:34
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. 

Rishabh Dugar:
20130619 06:09:57
running(40)n then gives me wa,,i have checked my code for the following as well;;

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