Without coupons, the total cost required to buy all the items is \(\sum_{i = 1}^N A_i\) yen. From this state, consider using coupons one by one. Every time you use a coupon, the price of the item you used it for is reduced, and the total cost required to buy all the items decreases accordingly. Specifically, every time a coupon is used, the price of the item it is used for changes as follows. Let \(a\) be the price of the item before using the coupon.

1. If \(a \geq X\), then the price changes to \(a-X\) yen; i.e. it decreases by \(X\) yen.
2. If \(0 \lt a \lt X\), then the price changes to \(0\) yen; i.e. it decreases by \(a\) yen.

If \(a=0\), then the price of the items remains unchanged: it’s still \(0\) yen.

In order to reduce the cost as much as possible, we should apply coupons first to items that potentially reduces the prices more. In other words,

• we should first apply the discount of type 1. above as many times as possible;
• then we should apply the discount of type 2. above as many times as possible, with the items with larger potential discount applying first.

By simulating this procedures, the answer for this problem is obtained.

However, under the Constraints of this problem, the number of coupons \(K\) can be as large as \(10^9\), so we have to simulate efficiently in order to fit in the time limit. We will now describe the details of the algorithm.

First, we first find how many times the discount of type 1. is applied without naively simulating. If we had an infinite number of coupons, then we could apply a discount of type 1. to the \(i\)-th item at most \(\lfloor \frac{A_i}{X} \rfloor\) times (where \(\lfloor x \rfloor\) denotes the maximum integer not exceeding \(x\)). Therefore, (if we had an infinite number of coupons) we could apply a discount of type 1. to all the items at most \(\sum_{i = 1} ^N \lfloor \frac{A_i}{X} \rfloor\) times in total. Considering the actual number of coupons you have, a discount of type 1. is applied \(m := \min \lbrace \sum_{i = 1} ^N \lfloor \frac{A_i}{X} \rfloor, K \rbrace\) times. Therefore, as a result of discounts of type 1. as much as possible, \(m\) number of coupons is consumed, and the total cost for all the items is reduced by \(mX\) yen.

If coupons still remain after \(m\) times of discounts of type 1., then apply discounts of type 2. to many items as possible, prioritizing the item with the highest current price. Since each item \(i\) has already been discounted down to \(A_i \bmod X\) yen (where \(A_i \bmod X\) denotes the remainder when dividing \(A_i\) by \(X\)), it can be implemented by sorting the items by the key \(A_i \bmod X\) and inspect them in the decreasing order of that value.

Therefore, the problem has been solved in a total of \(\mathrm{O}(N \log N)\) time.

Here is a sample code in C++.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, k, x;
ll a[200005];

int main(void)
{
  cin >> n >> k >> x;
  for(int i = 1; i <= n; i++) cin >> a[i];
  
  ll ans = 0;
  for(int i = 1; i <= n; i++) ans += a[i];
  
  ll m = 0;
  for(int i = 1; i <= n; i++) m += a[i]/x;
  m = min(m, k);
  ans -= m*x, k -= m;
  
  for(int i = 1; i <= n; i++) a[i] %= x;
  sort(a+1, a+n+1);
  
  for(int i = n; i >= 1; i--){
    if(k == 0) break;
    ans -= a[i], k--;
  }
  
  cout << ans << endl;
  
  return 0;
}