#include <iostream>
using namespace std;

int remain=1000000000,wine,b_size;
struct bottle
{
    int bmin;
    int bmax;
}b[100];  

int cmp(struct bottle *x,struct bottle *y)
{
    if(y->bmin > x->bmin) return 1;
    else return 0;
}


bool dp(int bmax,int bmin,int i)
{
    if(bmin+b[b_size-1].bmin>wine)
    {
        if(bmax>=wine) return true;
        else
        {
            remain=remain<(wine-bmax)?remain:(wine-bmax);
            return false;
        }
    }
    else
    {
        for(int j=i;j<b_size;j++)
        {
            if(bmin+b[j].bmin<=wine)
                if(dp(bmax+b[j].bmax,bmin+b[j].bmin,j)) return true;
        }
        return false;
    }
}


int main()
{
    cin>>wine>>b_size;
    wine=wine*1000;
    for(int i=0;i<b_size;i++) cin>>b[i].bmin>>b[i].bmax;
    qsort(b,b_size,sizeof(b[0]),(int(*)(const void *,const void *))cmp);
    if(dp(0,0,0)) cout<<0<<endl;
    else cout<<remain<<endl;
    return 0;
}