#include <iostream>

using namespace std;

bool f[100005];
int cnt[100005], a[15], b[15];

int main()
{
    int i, j, cash, n, temp;
    while(scanf("%d%d", &cash, &n) != EOF)
    {
        for(i = 0; i < n; i++)
                scanf("%d%d", &a[i], &b[i]);
        if(!cash || !n)
            printf("0\n");
        else
        {
            temp = 0;
            memset(f, 0, sizeof(f));
            f[0] = 1;
            for(i = 0; i < n; i++)
            {
                memset(cnt, 0, sizeof(cnt));
                for(j = b[i]; j <= cash; j++)
                {
                    if(!f[j] && f[j - b[i]] && cnt[j - b[i]] < a[i])
                    {
                        f[j] = 1;
                        cnt[j] = cnt[j - b[i]] + 1;
                        if(temp < j)
                            temp = j;
                    }
                }
            }
	        printf("%d\n", temp);
        }
    }
    return 0;
}