Solution for the Flowers Puzzle at Interviewstreet.com
/********************************/
All test cases passed
/********************************/
import java.math.BigInteger;
import java.util.*;
public class Solution {
static long result;
public long solve(ArrayList<Long> cost, int noOfFlowers, int noOfFriends) {
long finalCost = 0L;
int friendsCompleted = 0;
int[] personFlowers = new int[noOfFriends];
for(int i=cost.size()-1;i>=0;i--) {
finalCost += (++personFlowers[(friendsCompleted % noOfFriends)])*(cost.get(i)) ;
++friendsCompleted;
// System.out.println(finalCost);
}
return finalCost;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int N;
int K;
ArrayList<Long> cost = new ArrayList<Long>();
Scanner in = new Scanner(System.in);
Solution s= new Solution();
N = in.nextInt();
K = in.nextInt();
for(int i=0;i<N;i++) {
cost.add(in.nextLong());
}
Collections.sort(cost);
System.out.println( s.solve(cost, N, K) );
}
}