#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 50;
const long double eps = (1e-12);
const int logn = 21;
const double Pi = acos(-1.0);
const long long pp = 1000000000 + 7;
int lowbit(int x) { return x & (-x); }
const long long BLOCK = sqrt(MAXN);
const long long INF = 1e18;
long long p[MAXN];
long long c[MAXN];
long long pre[3005][3005];
long long poi[3005];
vector<vector<long long> > g(MAXN);
signed main() {
  long long n, m;
  scanf("%lld%lld", &n, &m);
  long long cnt = 0;
  multiset<long long> st;
  for (long long i = 1; i <= n; i++) {
    scanf("%lld%lld", &p[i], &c[i]);
    g[p[i]].push_back(c[i]);
    if (p[i] == 1)
      cnt++;
    else
      st.insert(c[i]);
  }
  for (long long i = 1; i <= m; i++) {
    sort(g[i].begin(), g[i].end());
  }
  for (long long i = 1; i <= m; i++) {
    for (long long j = 0; j < g[i].size(); j++) {
      pre[i][j + 1] = pre[i][j] + g[i][j];
    }
  }
  long long ans = INF;
  for (long long i = n / 2 + 1; i >= cnt; i--) {
    long long tmp = 0;
    if ((m - 1) * (i - 1) < n - i) {
      continue;
    }
    long long ned = i - cnt;
    for (long long j = 2; j <= m; j++) {
      long long sz = g[j].size();
      if (sz > i - 1) {
        long long len = sz - (i - 1);
        tmp += pre[j][len];
        ned -= len;
        for (long long k = poi[j]; k < len; k++) {
          st.erase(st.find(g[j][k]));
        }
        poi[j] = len;
      }
    }
    for (auto a : st) {
      if (ned <= 0) break;
      tmp += a;
      ned--;
    }
    if (ned <= 0) ans = min(ans, tmp);
  }
  if (cnt > n / 2 + 1) ans = 0;
  printf("%lld", ans);
}
