#include <iostream>
using namespace std;

struct mac
{
    int n;
    int d;
}nd[11];
bool dp[100010];

int main()
{
    int i,j,n,cash,k,cmax;
    while(scanf("%d%d",&cash,&n) != EOF)
    {
        for(i = 0;i < n;i++)    scanf("%d%d",&nd[i].n,&nd[i].d);
        if(cash == 0 || n == 0)
        {
            printf("0\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        dp[0] = true;
        for(i = 0,cmax = 0;i < n;i++)
            for(j = cmax;j >= 0;j--)
                if(dp[j])
                    for(k = 1;k <= nd[i].n;k++)
                    {
                        int temp = j + k*nd[i].d;
                        if(temp > cash) break;
                        dp[temp] = true;
                        if(temp > cmax) cmax = temp;
                    }
        printf("%d\n",cmax);
    }
    return 0;
}