以下、「整数 \(v\) が書かれたカード」のことを簡単に整数 \(v\) と呼びます。

まず、初期手札に各整数が何枚ずつあるかという情報を求めます。 具体的には「整数 \(v_i\) を \(f_i\) 枚持っている」という情報を表す列 \(((v_0, f_0), (v_1, f_1), (v_2, f_2), \ldots, (v_{k-1}, f_{k-1}))\) を求めます。 ここで、一般性を失わず \(f_0, f_1, \ldots, f_{k-1}\) はすべて正、かつ、\(v_0 \lt v_1 \lt \cdots \lt v_{k-1}\) とします。 この列は、連想配列等を用いて \(O(N \log N)\) 時間で求められます。

最終的に手札に残る整数の総和を最小化する上では、 \(2\) 枚目以降に出す整数については、最後に出した整数と同じ整数が手札に残っているならそれを出すとして良いです。 よって、\(2\) 枚目以降に出す整数は随時一通りに決定することができるため、高橋君に実質的に残される選択の余地は「 \(1\) 枚目に出す整数を何にするか」だけです。

初期手札に \(0\) 以上 \(M-1\) 以下の整数がそれぞれ \(1\) 枚以上ある場合、すなわち \(k = M\) の場合は、\(1\) 枚目に出す整数を何にするかによらず、最終的に手札を \(0\) 枚にすることができます。つまり、この時の出力すべき答えは \(0\) です。

以下、 \(k \leq M-1\) とします。

「 \(1\) 枚目に出す整数を \(v_i\) にしたときに最終的な手札に残る整数の総和」を \(s_i\)で表し、この \(s_0, s_1, \ldots, s_{k-1}\) を求めることを考えます。 \(1\) 枚目に出す整数を \(v_i\) にしたとき、

• \(v_{(i+1) \bmod k} \neq (v_i + 1) \bmod M\) ならば、初期手札（総和 \(\sum_{j = 0}^k v_jf_j\) ）から整数 \(v_i\) を \(f_i\) 枚出したあと、それ以上カードを出せないので \(s_i = (\sum_{j = 0}^k v_jf_j) - v_if_i\) です。
• \(v_{(i+1) \bmod k} = (v_i + 1) \bmod M\) ならば、初期手札から整数 \(v_i\) を \(f_i\) 枚出したあと、さらに「 \(1\) 枚目に出す整数を \((v_i + 1) \bmod M\) にしたとき」の操作を続けられるので、\(s_i = s_{(i+1) \bmod k} - v_if_i\) です。

よって、\(v_{(p+1) \bmod k} \neq (v_p + 1) \bmod M\) を満たすある \(p\) からはじめ、\(i = p, p-1, p-2, \ldots, 1, 0, k-1, k-2, \ldots, p+1\) の順に、各 \(s_i\) を計算することが全体で \(O(N)\) 時間でできます。 \(\min \lbrace s_0, s_1, \ldots, s_{k-1} \rbrace\) が出力すべき答えです。

以上より、本問題を \(O(N \log N)\) 時間で求められます。

以下に、C++言語による正解例を記載します。

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;

ll s[200005];

int main(void)
{
  ll n, m, a, sum = 0; 
  map<ll, ll> mp;
  
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a;
    mp[a]++;
    sum += a;
  }  
  vector<pair<ll, ll>> vec;
  for(auto p : mp) vec.push_back(p);
  int k = vec.size();
  
  if(k == m){
    cout << 0 << endl;
    return 0;
  }
  
  int p;
  for(int i = 0; i < k; i++){
    if(vec[(i+1)%k].first != (vec[i].first+1)%m){
      p = i;
      break;
    }
  }
  
  for(int i = 0; i < k; i++){
    int j = (p-i+k)%k;
    s[j] = sum;
    if(vec[(j+1)%k].first == (vec[j].first+1)%m) s[j] = s[(j+1)%k];
    s[j] -= vec[j].first * vec[j].second;
  }
  
  ll ans = sum;
  for(int i = 0; i < k; i++) ans = min(ans, s[i]);
  cout << ans << endl;
  
  return 0;
}