### PROBLEM LINK

### Panel Members

**Problem Setter:** Suhash

**Problem Tester:**

**Editorialist:** Sunny Aggarwal

**Contest Admin:**

**Russian Translator:**

**Mandarin Translator:**

**Vietnamese Translator:**

**Language Verifier:**

### DIFFICULTY:

Easy

### PREREQUISITES:

Basic Mathematics, Prefix Sum, Sorting, Dynamic Programming.

### PROBLEM:

Given a list of N coins of possibly different denominations. We can pay amount equivalent to any 1 coin and can acquire that coin. In addition once we have paid for a coin, we can choose atmost K more coins and can acquire those for free. What is the minimum amount required to acquire all the N coins for a given K ?

**Note that a coin can be acquired only once.**

### EXPLANATION

It is easy to notice that at a cost of 1 coin, we can acquire at most K+1 coins. Therefore, in order to acquire all the N coins we will be choosing \lceil N/(K+1)\rceil coins and the cost of choosing coins will be minimum if we choose smallest \lceil N/(K+1)\rceil coins. Smallest \lceil N/(K+1)\rceil coins can be found by simply sorting all the N values in increasing order.

**C++ code:**

int main() { int n, k; cin >> n >> k; int arr[n]; for(int i=0; i<=n-1; i++) { cin >> arr[i]; } sort(arr, arr+n); int coins_needed = ceil(1.0*n/(k+1)); int ans = 0; for(int i=0; i<=coins_needed-1; i++) { ans += arr[i]; } cout << ans << "\n"; return 0; }

As we are asked to find the above answer for many different values of K, we have to compute it fast. For the purpose to serve, we can maintain a prefix sum array after sorting all the N values and can answer queries easily.

**C++ code:**

int main() { int n, q, k; cin >> n >> q; int arr[n]; for(int i=0; i<=n-1; i++) { cin >> arr[i]; } sort(arr, arr+n); for(int i=1; i<=n-1; i++) { arr[i] += arr[i-1]; } while( q-- ) { cin >> k; int coins_needed = ceil(1.0*n/(k+1)); int ans = arr[coins_needed-1]; cout << ans << "\n"; } return 0; }

### COMPLEXITY

O(Nlog(N) + Q)