#include <bits/stdc++.h> using namespace std; int n, m; int v[1001], w[1001], a[1001][1001]; 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(j<w[i]) { a[i][j]=a[i-1][j]; } else { a[i][j]=max(a[i-1][j], a[i-1][j-w[i]]+v[i]); } } } cout << a[n][m] << endl; return 0; } //2 3 //5 4 //5 5