RT，不会四边形不等式所以写了个wqs二分，但一直 WA

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 3e3 + 5;

LL a[kMaxN], v[kMaxN][kMaxN], s[kMaxN], f[kMaxN], g[kMaxN], n, m;

LL P(int x, int y, int t) {
  if (t > y || t < x) {
    return 1e9;
  }
  return a[y] * (y - t + 1) - (s[y] - s[t - 1]) + (s[t - 1] - s[x - 1]) - (t - x) * a[x];
}

LL S(int x, int y) {
  int l = x, r = y + 1;
  for (int mid; l < r; a[mid] - a[x] >= a[y] - a[mid] ? r = mid : l = mid + 1) {
    mid = l + r >> 1;
  }
  return min(P(x, y, r), P(x, y, r - 1));
}

LL V(int x) {
  return f[x] + s[n] - s[x] - (n - x) * a[x];
}

int C(int x) {
  int ans = 0;
  f[0] = 1e9;
  for (int i = 1; i <= n; i++) {
    f[i] = a[i] * i - s[i] - x;
    g[i] = 1;
    for (int k = 1; k < i; k++) {
      if (f[i] > f[k] + v[k][i] - x) {
        f[i] = f[k] + v[k][i] - x;
        g[i] = g[k] + 1;
      } else if (f[i] == f[k] + v[k][i] - x) {
        g[i] = min(g[i], g[k] + 1);
      }
    }
    (V(i) + g[i] * x < V(ans) + g[ans] * x || V(i) + g[i] * x == V(ans) + g[ans] * x && g[i] < g[ans]) && (ans = i);
  }
  return ans;
}

int main() {
  // freopen("input.in", "r", stdin);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + a[i];
  }
  a[n + 1] = 1e9;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      v[i][j] = S(i, j);
    }
  }
  LL l = -1e9, r = 1e9, ans = 1e14;
  for (int mid; l < r; g[C(mid)] <= m ? l = mid : r = mid - 1) {
    mid = l + r + 1 >> 1;
  }
  int x = C(l);
  cout << V(x) + g[x] * l;
  return 0;
}