#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
const long long inf = 1ll << 60;
long long n, m, k;
struct Node {
  long long id, p, c;
  Node(long long id = 0, long long p = 0, long long c = 0)
      : id(id), p(p), c(c){};
  friend bool operator<(Node a, Node b) { return a.c < b.c; }
};
vector<Node> party[maxn];
Node pool[maxn];
int use[maxn];
int res[maxn];
int chk() {
  memset(res, 0, sizeof(res));
  for (int i = 1; i <= n; i++) {
    if (use[pool[i].id] == 1) {
      res[1]++;
    } else {
      res[pool[i].p]++;
    }
  }
  for (int i = 2; i <= m; i++) {
    if (res[1] <= res[i]) return 0;
  }
  return 1;
}
long long solve1(int t) {
  t -= party[1].size();
  memset(use, 0, sizeof(use));
  long long cost = 0, tot = 0;
  for (int pt = 2; pt <= m; pt++) {
    int sz = party[pt].size();
    for (int j = 0; j < party[pt].size(); j++) {
      if (tot == t || sz <= t + party[1].size()) break;
      use[party[pt][j].id] = 1;
      tot++;
      sz--;
      cost += party[pt][j].c;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (tot == t) break;
    if (pool[i].p == 1) continue;
    if (!use[pool[i].id]) {
      use[pool[i].id] = 1;
      tot++;
      cost += pool[i].c;
    }
  }
  if (chk()) return cost;
  return inf;
}
long long solve2(int t) {
  t -= party[1].size();
  memset(use, 0, sizeof(use));
  long long cost = 0, tot = 0;
  for (int pt = 2; pt <= m; pt++) {
    int sz = party[pt].size();
    for (int j = 0; j < party[pt].size(); j++) {
      if (tot == t || sz < t + party[1].size()) break;
      use[party[pt][j].id] = 1;
      tot++;
      sz--;
      cost += party[pt][j].c;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (tot == t) break;
    if (pool[i].p == 1) continue;
    if (!use[pool[i].id]) {
      use[pool[i].id] = 1;
      tot++;
      cost += pool[i].c;
    }
  }
  if (chk()) return cost;
  return inf;
}
int main() {
  cin >> n >> m;
  int p, c;
  for (int i = 1; i <= n; i++) {
    cin >> p >> c;
    pool[i] = Node(i, p, c);
  }
  sort(pool + 1, pool + n + 1);
  for (int i = 1; i <= n; i++) {
    party[pool[i].p].push_back(pool[i]);
  }
  long long ans = inf;
  for (int t = party[1].size(); t <= n; t++) {
    ans = min(ans, min(solve1(t), solve2(t)));
  }
  cout << ans;
  return 0;
}
