#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct rock
{
    long long size0;
    long long value;
};
rock rocks[10000005];
long long dp[10000005];
long long volume, n;
bool cmp(rock r1, rock r2)
{
    return r1.size0 < r2.size0;
}
int main()
{
    int cnt = 0;
 //   cin >> volume >> n;
    scanf("%d%d", &volume, &n);
    int min_size = 10000000;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
  //      cin >> a >> b;
        scanf("%d%d", &a, &b);
        if (a > volume)
            continue;
        int num = volume / a;
        min_size = min(min_size, a);
        for (int j = 0; j < num; j++)
        {
            rocks[cnt].size0 = a;
            rocks[cnt].value = b;
            cnt++;
        }
    }
    sort(rocks, rocks + cnt, cmp);
    for (int i = 0; i <= volume; i++)
        dp[i] = 0;
    for (int j = 0; j < cnt; j++)
    {
        for (int i = volume; i >= min_size; i--)
        {
            if (i >= rocks[j].size0)
                dp[i] = max(dp[i], dp[i - rocks[j].size0] + rocks[j].value);
            else
                break;
        }
    }
    cout << dp[volume] << endl;
    return 0;
}