#include <bits/stdc++.h>
using namespace std;
int n, w[30+10],c[30+10], f[200+10], v;
int main() {
cin >>v>> n;
for (int i = 1; i <= n; i++)
cin>>w[i]>>c[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= v; j++)
if(j>=w[i])
f[j] =max(f[j],f[j-w[i]]+c[i]);
cout <<"max="<<f[v];
}