#include <bits/stdc++.h> using namespace std; int dp[205], w[35], c[35], m, n; int main() { cin >> m >> n; for (int i = 1; i <= n; ++ i){ cin >> w[i] >> c[i]; } for (int i = 1; i <= m; ++ i){ for (int j = 1; j <= m; ++ j){ dp[j] = max(dp[j],dp[j - w[i]] + c[i]); } } cout << dp[m]; return 0; }