## Problem

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**gold plates. Each gold plate costs exactly 1

_{i}**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**Nimbdas, and take away all the gold plates in that house (Hence, he also ends up looting this house)._{i} - 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**denotes the number of gold plates in the

_{i}**i**house. The third line of input consists of a single integer

^{th}**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**line denotes the value of K for the

^{th}**i**query.

^{th}### Output

Output exactly **Q** integers on separate lines, where the output on the **i ^{th}** line denotes the answer for the

**i**value of

^{th}**K**.

### Constraints

**1**≤**N**≤**10**^{5}**1**≤**Q**≤**10**^{5}**0**≤**K**≤**N-1****1**≤**A**≤_{i}**10**^{4}

### Sample Input 1

```
4
3 2 1 4
2
2
```

### Sample Output 1

```
10
3
```

## Bhallaladeva – CodeChef Solution in JAVA

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] A = readArray(sc); int[] K = readArray(sc); Arrays.stream(solve(A, K)).forEach(System.out::println); sc.close(); } static int[] readArray(Scanner sc) { int size = sc.nextInt(); int[] result = new int[size]; for (int i = 0; i < result.length; i++) { result[i] = sc.nextInt(); } return result; } static int[] solve(int[] A, int[] K) { Arrays.sort(A); int[] prefixSums = buildPrefixSums(A); int[] result = new int[K.length]; for (int i = 0; i < result.length; i++) { result[i] = prefixSums[divideToCeil(prefixSums.length, K[i] + 1) - 1]; } return result; } static int[] buildPrefixSums(int[] A) { int prefixSum = 0; int[] prefixSums = new int[A.length]; for (int i = 0; i < prefixSums.length; i++) { prefixSum += A[i]; prefixSums[i] = prefixSum; } return prefixSums; } static int divideToCeil(int x, int y) { return x / y + (x % y == 0 ? 0 : 1); } }

** Disclaimer: The above Problem (Bhallaladeva ) is generated by** CodeChef but the solution is provided by

**Chase2learn**.This tutorial is only for

**Educational**and

**Learning**purpose.