#include <iostream>
#include <cstdio>
using namespace std;
int dist[105000];
int value[15];
int acount[15];
int n , m ;

void ZeroOnePack(int v)
{
    for(int i = m; i>= v; i --)
    {
        dist[i] = max(dist[i] , dist[i-v]+v);
    }
}

void CompletePack(int v)
{
    for(int i = v; i <= m; i ++)
    {
        dist[i] = max(dist[i] , dist[i-v]+v);
    }
}

void MultiPack(int v , int amount)
{
    if(v * amount >= m)
    {
        CompletePack(v);
    }
    else
    {
        int k = 1;
        int cnt = amount;
        while(k <= cnt)
        {
            ZeroOnePack(k*v);
            cnt -= k ;
            k *= 2;
        }
        if(cnt)
        ZeroOnePack(cnt*v);
    }
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(n == 0){
            printf("0\n");
            continue;
        }
        for(int i = 0; i < n; i ++)
        {
            scanf("%d %d",&acount[i],&value[i]);
        }
        for(int i = 0; i <= m; i ++)
        {
            dist[i] = 0;
        }
        for(int i = 0; i < n; i ++)
        {
            MultiPack(value[i] , acount[i]);
        }
        printf("%d\n",dist[m]);
    }
    return 0;
}