#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=10+2;
const int maxc=100000+100;

struct DE
{
    int k,n;
    bool operator<(const DE &a) const
    {
        return k>a.k;
    }
};
DE des[maxn];
int N,res;
int cash;
bool ss[maxc];

void work()
{
    memset(ss,0,sizeof(ss));
    ss[0]=1;
    for(int i=0;i<N;i++)
    {
        for(int j=cash;j>=0;j--)
        {
            if(ss[j])
            {
                for(int k=1;k<=des[i].n;k++)
                {
                    if(j+des[i].k*k<=cash)
                        ss[j+des[i].k*k]=1;
                }
            }
        }
    }
    for(int i=cash;i>=0;i--)
        if(ss[i])
        {
            res=i;
            break;
        }
}

int main()
{
    freopen("in.txt","r",stdin);
    while(~scanf("%d",&cash))
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d%d",&des[i].n,&des[i].k);
        work();
        printf("%d\n",res);
    }
    return 0;
}