#include<iostream> using namespace std; int dp[1001][101]; int w[101]; int v[101]; int main() { int n, m; while (cin >> n >> m) { for (int i = 0; i < m; i++) { cin >> w[i] >> v[i]; } for (int i = 0; i <= n; i++) { dp[i][0] = 0; } for (int i = 0; i < m; i++) { dp[0][i] = 0; } // 考虑0-m-1个商品中的总价值最大 for (int x = 1; x <= n; x++) { for (int y = 1; y <= m; y++) { if (x - w[y - 1] < 0) { dp[x][y] = dp[x][y - 1]; } else { dp[x][y] = max(dp[x][y - 1], dp[x - w[y - 1]][y - 1] + v[y - 1]); } } } cout << dp[n][m] << endl; } }