#include <bits/stdc++.h>
using namespace std;
int n,m;
int w[405],t[405];
int f[2000005];
int W[2000005],T[2000005];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>w[i];
	}
	int N = (1<<n)-1;
	for(int i=0;i<=N;i++){
		for(int j=1;j<=n;j++){
			if((i & (1<<(j-1)))==0)continue;
			W[i] += w[j];
			T[i] = max(T[i],t[j]);
		}
	}
	memset(f,0x3f,sizeof(f));
	f[0] = 0;
	for(int i=0;i<=N;i++){
		for(int j=i;;j=(i&(j-1))){
		//	cout<<j<<endl;
			if(W[i^j]<=m){
				f[i] = min(f[i],f[j]+T[i^j]);
			}
			if(j==0)break;
		}
	}
	cout<<f[N]<<endl;
	return 0;
}