Pleasing the Martian King

All submissions for this problem are available.
Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the dawn hour breakin' news on freakin' news :
Occassionally, the martian ministers feel the need to please their king. For this purpose, they give the king a trivial problem to solve and heap excessive praise upon him when he presents the correct solution.
This time they have given the king the following problem :
Given two positive integers n,k and n numbers a[1],a[2],...a[n] find the maximum of (b[1]a[1]+b[2]a[2]+.....b[n]a[n]) subject to the restrictions :
1) b[i] is either 1 or (1), for all i, 1<=i<=n.
2) Exactly k b[i]'s are 1. The remaining (nk) b[i]'s are (1).
To make the task even easier for the king, the ministers have given the king the sequence a[1],a[2],...a[n] sorted in nondecreasing order.
The king, being lazy, has outsourced the task to freakin' news. Your job is to do this task for freakin' news.
Input Format :
The first line of input contains a single integer n. The next line consists of n space seperated integers a[1], a[2], ... a[n]. The sequence a is guaranteed to be sorted in nondecreasing order.
Output Format :
On the only line of output, output a single integer : the maximum of (b[1]a[1]+b[2]a[2]+.....b[n]a[n]) subject to restrictions 1 and 2.
Constraints :
2<=n<=100
0<=k<=n
a[i]<=1000
The sequence a is sorted in nondecreasing order i.e. a[1]<=a[2]<=....<=a[n]
Sample Input :
2 1
4 4
Sample Output :
0
Sample Input :
2 0
2 5
Sample Output :
3
Explanation :
1 : There are two possibilities for the sequence b : (+1,1) and (1,+1). Both lead to sum 0.
2 : There is only one possibility for the sequence b : (1,1). This leads to the sum 3.
Author:  architk 
Tags  architk 
Date Added:  27032012 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions