クーポンを\(1\)枚も使わないとき、全商品を買うための合計費用は \(\sum_{i = 1}^N A_i\) 円です。 その状態からクーポンを \(1\) 枚ずつ使っていくことを考えます。クーポンを \(1\) 枚使用するたびに、使用対象となる商品の値段が減少し、それに伴って、全商品を買うための合計費用も減少します。 具体的には、クーポンを \(1\) 枚使うごとに、使用対象となる商品の値段が下記の通りに変わります（クーポン使用前の値段を \(a\) 円とします）。

1. \(a \geq X\) のとき、商品の値段は \(a-X\) 円に変わる。すなわち、\(X\) 円安くなる。
2. \(0 \lt a \lt X\) のとき、商品の値段は \(0\) 円に変わる。すなわち、\(a\) 円安くなる。

\(a = 0\) のときは、商品の値段は \(0\) 円のまま変わりません。

全商品を買うための合計費用を最小化するには、より多く値下げできる商品から優先的にクーポンを使用していけば良いです。 すなわち、

• まず、上記のタイプ 1. の値下げを可能な限り行い、
• その後、上記のタイプ 2. の値下げを、値下げできる金額が多いものから順に可能な限り行えば良いです。

それをシミュレーションすることで本問題の答えが得られます。

しかし、本問題の制約下では、手持ちのクーポンの枚数 \(K\) は最大で \(10^9\) 枚と非常に大きくなるので、実行制限時間に間に合わせるためには効率的にシミュレーションする必要があります。その方法を以下で述べます。

まず、タイプ 1. の値下げが何回行われることになるかを、愚直にシミュレーションすることなく求めます。 仮に手持ちのクーポンが無限にあると仮定すれば、\(i\) 番目の商品に対してタイプ 1. の値下げを行える回数の上限は \(\lfloor \frac{A_i}{X} \rfloor\) 回です（ \(\lfloor x \rfloor\) は \(x\) を超えない最大の整数）。 よって（クーポンが無限にあるなら）タイプ 1. の値下げを行える回数の上限は全商品合わせて \(\sum_{i = 1} ^N \lfloor \frac{A_i}{X} \rfloor\) 回です。 手持ちのクーポンの枚数も考慮すると、タイプ 1. の値下げが行われる回数は \(m := \min \lbrace \sum_{i = 1} ^N \lfloor \frac{A_i}{X} \rfloor, K \rbrace\) 回です。 したがって、タイプ 1. の値下げを可能な限り行った結果、\(m\) 枚のクーポンが消費され、全商品を買うための合計費用は \(mX\) 円安くなります。

タイプ 1. の値下げを \(m\) 回行った後、まだ手持ちのクーポンが残っていれば、現時点での値段の高いものから優先的にタイプ 2. の値下げを可能な限り行います。 この時点で各商品 \(i\) の値段はすでに \(A_i \bmod X\) 円にまで値下げされている（ \(A_i \bmod X\) は \(A_i\) を \(X\) で割ったあまりを表す）ことに注意すると、各商品を \(A_i \bmod X\) をキーとしてソートし、それが大きい商品から順に見ていけば良いです。

以上より、本問題を \(\mathrm{O}(N \log N)\) 時間で解くことができます。

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;
}