#include <bits/stdc++.h> using namespace std; int dp[105][1001], w[101], c[101]; int main() { int n, v; cin >> v >> n; for (int i = 0; i < n; i++) { cin >> w[i] >> c[i]; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= v; j++) { if (j >= w[i - 1]) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + c[i - 1]); } else dp[i][j] = dp[i - 1][j]; } } cout << "max=" << dp[n][v]; return 0; }