#include <iostream>
#include <fstream>
using namespace std;
int g, n, gr[5001], c[5001], castig[10001];
ifstream f("rucsac.in");
ofstream g1("rucsac.out");
void citire()
{
    f>>g>>n;
    for (int i=1;i<=n;i++)
    f>>gr[i]>>c[i];
}

int main ()
{   citire();
    for (int i=1;i<=n;i++)
    for (int j=g;j>=1;j--)
    if (gr[i]<=j)
    if (castig[j] < (castig[j-gr[i]] + c[i]))
        {castig[j]=castig[j-gr[i]] + c[i];
        }
    int suma=0;
    g1<<castig[g];
}