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