#include <bits/stdc++.h>
using namespace std;
struct Voter {
  int ID, needCoin;
  bool operator()(Voter a, Voter comp) const {
    return a.needCoin < comp.needCoin;
  }
};
vector<Voter> partyVote[3001];
vector<Voter> que;
bool vis[3001];
int Rank[3001];
int main() {
  int totVoter, totParty, voteTarg, $;
  int votesGet = 0, nowVotes, siz = 0, Left;
  long long _min = 9223372036854775807LL, _count;
  cin >> totVoter >> totParty;
  for (int i = 0; i < totVoter; i++) {
    cin >> voteTarg >> $;
    if (--voteTarg == 0)
      votesGet++;
    else {
      partyVote[voteTarg].push_back({i, $});
      que.push_back({i, $});
    }
  }
  for (int i = 0; i < totParty; i++) Rank[i] = i;
  sort(Rank, Rank + totParty, [](int a, int comp) {
    return partyVote[a].size() > partyVote[comp].size();
  });
  for (int i = 0; i < totParty; i++)
    sort(partyVote[i].begin(), partyVote[i].end(), Voter());
  sort(que.begin(), que.end(), Voter());
  siz = totVoter >> 1;
  for (int minNeeds = 0; minNeeds <= siz; minNeeds++) {
    nowVotes = votesGet;
    _count = 0;
    memset(vis, false, sizeof(vis));
    for (int i = 0; partyVote[Rank[i]].size() > minNeeds; i++)
      for (int j = 0; j < partyVote[Rank[i]].size() - minNeeds; j++) {
        _count += partyVote[Rank[i]][j].needCoin;
        nowVotes++;
        vis[partyVote[Rank[i]][j].ID] = true;
      }
    for (int i = 0; nowVotes <= minNeeds; i++) {
      if (vis[que[i].ID]) continue;
      nowVotes++;
      _count += que[i].needCoin;
    }
    if (_count < _min) _min = _count;
  }
  cout << _min << endl;
  return 0;
}
