#include <bits/stdc++.h> using namespace std; int dp[205] = {0}, w[35] = {0}, c[35] = {0}, 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 = w[i]; j <= m; ++ j){ dp[j] = max(dp[j],dp[j - w[i]] + c[i]); } } cout << "max=" << dp[m]; return 0; }