#include <iostream>
#include <memory.h>
using namespace std;

const int maxofn=10;
const int maxofcash=100000;

struct data1{
    int num;
    int at;
}bills[maxofn];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int cash;
    int n;
    int i,j,k;
    bool visit[maxofcash+1];
    while(cin>>cash>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>bills[i].num>>bills[i].at;
        }
        memset(visit,0,sizeof(visit));
        visit[0]=true;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=cash;j++)
            {
                if(visit[j])
                {
                    for(k=0;k<=bills[i].num;k++)
                    {
                        if(j+k*bills[i].at<=cash)
                        {
                            visit[j+k*bills[i].at]=true;
                        }else{
                            break;
                        }
                    }
                }
            }
        }
        for(i=0;i<=cash;i++)
        {
            if(visit[cash-i]) break;
        }
        cout<<cash-i<<endl;
    }
    return 0;
}