#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int a[5005];
int b[5005];
int v[10005];
int main()
{

    int n, k;
    in >> n >> k;
    for(int i = 1; i <= k; i ++)
        in >> a[i] >> b[i];
    int mx = -1;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = k - a[i]; j >= 0; j --)
        {
            if(v[j + a[i]] < v[j] + b[i])
            {
                v[j + a[i]] = v[j] + b[i];
                mx = max(mx, v[j + a[i]]);
            }
        }
    }
    out << mx;
    return 0;
}