#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 20
#define maxf 1<<20
 
int limit,n;
int a[maxn],b[maxn];
int t[maxf],w[maxf],dp[maxf];
 
int main(){
    scanf("%d%d",&limit,&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    for (int i=1;i<(1<<n);i++)
        for (int j=0;j<n;j++)
            if (i&(1<<j)){
                t[i]=max(t[i],a[j+1]);
                w[i]+=b[j+1];
            }
    memset(dp,127,sizeof(dp)),dp[0]=0;
    for (int i=1;i<(1<<n);i++)
        for (int j=i;j;j=i&(j-1))
            if (w[j]<=limit) dp[i]=min(dp[i],t[j]+dp[i^j]);
    printf("%d\n",dp[(1<<n)-1]);
    return 0;
}