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