#include using namespace std; /* 知识点内容:动态规则0-1背包问题 文档内容参考: https://www.cnblogs.com/aiguona/p/7274222.html */ using namespace std; int w[105], val[105]; int dp[105][1005]; int main() { int t, m; cin >> t >> m; for (int i = 1; i <= m; i++) cin >> w[i] >> val[i]; for (int i = 1; i <= m; i++) //物品 for (int j = t; j >= 0; j--) //容量 { if (j >= w[i]) dp[i][j] = max(dp[i - 1][j - w[i]] + val[i], dp[i - 1][j]); else dp[i][j] = dp[i - 1][j]; } cout << dp[m][t] << endl; return 0; }