#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() #define pb push_back typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。 /* 10 4 2 1 3 3 4 5 7 9 */ int n,m; cin >> n >> m; vector<int> w(n),c(n); for(int i = 0; i < n; ++i) { cin >> w[i] >> c[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,0)); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++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 << dp[n][m] << '\n'; return 0; }