#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 20,mod = 1e9+7,INF = 0x3f3f3f3f;
//__gcd()
ll a[N][N],b[N],w[N],v[N],num[N],summ[1<<20],fa[N];
ll t,ans,sum,k,pre,res,cnt,total,flat,h,n,m,x,y,z,minn = 1e9,maxn;
ll dp[1<<20],g[1<<20];
ll init()
{
	for(int S=0;S<(1<<n);S++)
		for(int i=1;i<=n;i++){
			summ[S] += ((S&(1<<(i-1))) != 0)*w[i];
			g[S] = max(g[S],((S&(1<<(i-1))) != 0)*v[i]);
		}
}
void solve()
{
	cin >> m >> n;
	memset(dp,INF,sizeof(dp));
	dp[0] = 0;
	for(int i=1;i<=n;i++){
		cin >> v[i] >> w[i];
		dp[1<<(i-1)] = v[i];
	}
	init();
	for(int S=0;S<(1<<n);S++)
		for(int j=S;j;j=((j-1)&S)){		//遍历集合S中的子集j 
			if(summ[j] > m)
				continue;
			dp[S] = min(dp[S],dp[S-j]+g[j]);
		}
	cout << dp[(1<<n)-1]; 
} 
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	int t; cin >> t;
//	while(t--)
		solve();
	return 0;
}