Bhallaladeva

All submissions for this problem are available.
Bhallaladeva was an evil king who ruled the kingdom of Maahishmati. He wanted to erect a 100ft golden statue of himself and he looted gold from several places for this. He even looted his own people, by using the following unfair strategy:
There are N houses in Maahishmati, and the i^{th} house has A_{i} gold plates. Each gold plate costs exactly 1 Nimbda, which is the unit of currency in the kingdom of Maahishmati. Bhallaladeva would choose an integer K, and loots all the houses in several steps. In each step:
 He would choose a house i which hasn't been looted yet, pay the owner exactly A_{i} Nimbdas, and take away all the gold plates in that house (Hence, he also ends up looting this house).
 He would now choose atmost K houses which haven't been looted yet and take away all the gold plates from these houses without paying a single Nimbda (Yes, he takes all of them for free).
He repeats the above steps until all the N houses have been looted. Your task is to devise a strategy for Bhallaladeva to loot the houses in some order, so that the number of nimbdas he has to pay is minimium. You'll also be given multiple values of K (Q of them to be precise), and you need to find the minimum number of nimbdas for each of these values.
Input
The first line of input consists of a single integer N denoting the number of houses in Maahishmati. The second line of input consists of N space separated integers denoting A_{1}, A_{2}, ..., A_{N}, where A_{i} denotes the number of gold plates in the i^{th} house. The third line of input consists of a single integer Q denoting the number of values of K to follow. Each of the following Q lines consist of a single integer, where the value on the i^{th} line denotes the value of K for the i^{th} query.
Output
Output exactly Q integers on separate lines, where the output on the i^{th} line denotes the answer for the i^{th} value of K.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 0 ≤ K ≤ N1
 1 ≤ A_{i} ≤ 10^{4}
Example
Input: 4 3 2 1 4 2 0 2 Output: 10 3
Explanation
For the first query, K = 0. Hence, Bhallaladeva cannot take gold plates from any of the houses for free. It will cost him 3 + 2 + 1 + 4 = 10 nimbdas.
For the second query, K = 2. In the first step Bhallaladeva can pay 2 nimbdas for gold plates in house number 2, and take the gold in houses 1 and 4 for free (Note that house 1 has 3 gold plates and house 4 has 4 gold plates). Now, he has looted houses 1, 2 & 4. Now in the second step, he loots house 3, by paying 1 nimbda. Hence, the total cost = 1 + 2 = 3. Note that there might be multiple ways to achieve the minimum cost, and we have explained only one of them.
Author:  suh_ash2008 
Editorial  http://discuss.codechef.com/problems/AMR15D 
Tags  acmamr15, basicmath, dynamicprogramming, easy, sorting, suh_ash2008 
Date Added:  11102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 