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

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