#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "
#define cout(n) cout<<fixed<<setprecision(n)
int main(){
  ll n,m;
  cin>>n>>m;
  vector<P> v(n);//まとめ
  vector<ll> vote(m,0);//政党ごと
  ll ina,inb;
  FOR(i,0,n){
    cin>>ina>>inb;
    vote[ina-1]++;
    v[i] = make_pair(inb,ina);
  }
  P max=make_pair(0,0);
  FOR(i,0,m){
    if(max.first<vote[i]) max=make_pair(vote[i],i+1);
  }
  FOR(i,0,n){
    if(v[i].second==max.second) v[i].first=v[i].first%2 + v[i].first/2;
  }
  sort(v.begin(),v.end());
  pair<int,int> sorti=make_pair(0,0);
  FOR(i,1,n){
    if(v[i].first==sorti.first&& sorti.second==max.second){
      v.erase(v.begin()+i);
      v.insert(v.begin()+sorti.second, sorti.first);
    }
    else{
      sorti = make_pair(v[i].first,i);
    }
  }
  reverse(v.begin()+sorti.second+1,v.end());

  FOR(i,0,n){
    cout<<v[i].first<<" party="<<v[i].second<<endl;
  }

  ll cost = 0;
  ll voteTo1 = vote[0];
  ll x=0;
  while(max.first>voteTo1){
    cost += v[x].first;
    if(v[x].second==max.second){
      cost += v[x].first;
      voteTo1++;
    }
    x++;
    voteTo1++;
    cout<<"cost="<<cost<<" x="<<x<<endl;
  }
  ll inst=x;
  if(max.first==voteTo1){
    while(x<n){
      if(v[inst].second!=max.second&&v[x].first<v[inst].first*2){
        cost+=v[x].first;
        break;
      }
      if(x==n-1){
        cost+=v[inst].first*2;
      }
      x++;
    }
  }
  if(max.second==1) cout<<0<<endl;
  else cout<<cost<<endl;
}
