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