#include <iostream>
using namespace std;
const int N = 10010;
int f[N];
int main()
{
int m, n; cin >> m >> n;
for(int i = 1; i <= n; i ++ ){
int v, w; cin >> w >> v;
for(int j = v; j <= m; j ++ )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}