//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1<<17;
int w,n,t[N];
struct Node{int w,t;}node[N];
int main(){
    scanf("%d%d",&w,&n);
    memset(t,0x3f,sizeof(t));
    for(int i=0;i<n;i++)scanf("%d%d",&node[i].t,&node[i].w);
    for(int i=1;i<(1<<n);i++){
        int temp=0,tempw=0;
        for(int j=0;j<n;j++)if(i&(1<<j))temp=max(temp,node[j].t),tempw+=node[j].w;
        if(tempw<=w)t[i]=temp;
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=i;j;j=(j-1)&i)
            t[i]=min(t[i],t[j]+t[i^j]);
    }printf("%d\n",t[(1<<n)-1]);
}