#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%2][j]=a[(i-1)%2][j]; } else { a[i%2][j]=max(a[(i-1)%2][j], a[(i-1)%2][j-w[i]]+v[i]); } } } cout << a[n%2][m%2] << endl; return 0; } //2 3 //5 4 //5 5