#include <bits/stdc++.h>
using namespace std;
int n,m,p,c;
vector <int> g[1005];//g[i]表示升级第i种武器的每一种材料所需金币
long long ans=9e18;
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>p>>c;
        g[p].push_back(c);
    }
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
    }
    for(int i=g[1].size();i<=m/2+1;i++){
        long long sum=0;//需要多少金币
        int cnt=0;//记录一下改了多少种材料
        vector <int> b;
        for(int j=2;j<=n;j++){
            int d=max(0,int(g[j].size()-i+1));
            cnt+=d;
            for(int k=0;k<g[j].size();k++){
                if (k<d){
                    sum+=g[j][k];
                }else{
                    b.push_back(g[j][k]);
                }
            }
        }
        if (cnt+g[1].size()<i){
            sort(b.begin(),b.end());
            for(int j=0;j<i-cnt-g[1].size();j++){
                sum+=b[j];
            }
        }
        ans=min(ans,sum);
    }
    cout<<ans;
	return 0;
}

using namespace std;
int n,m,p,c;
long long ans;
vector<int> g[1005];
int main(){
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p>>c;
		g[p].push_back(c);
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end());
	}
	for(int i=g[1].size();i<=m/2+1;i++){
		long long sum=0;
		int cnt=0;
		vector<int> b;
		for(int j=2;j<=n;j++){
			if(g[j].size()<i){
				continue;
			}
			int d=max(0,(int)g[j].size()-i+1);
			cnt+=d;
			for(int k=0;k<d;k++){
				if(k<d){
					sum+=g[j][k];
				}else{
					b.push_back(g[j][k]);
				}
			}
		}
		if(cnt+g[1].size()<i){
			sort(b.begin(),b.end());
			for(int j=0;j<i-cnt-g[1].size();j++){
				sum+=b[j];
			}
		}
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}