#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 <= n; ++ i){ for (int j = m; j >= w[i]; -- j){ dp[j] = max(dp[j],dp[j - w[i]] + c[i]); } } cout << dp[m]; return 0; }