dp[i][w] :
i 番目までの品物の中から (選ぶ、選ばない 選択)
重さが w を超えないように選んだときの、
価値の総和の最大値
// 入力
ll n, W; //荷物の数、許容容量
ll weight[110], value[110]; //重さ、価値
ll dp[110][10010]; //個数、重さ
int main() {
cin >> n >> W;
for (ll i = 0; i < n; ++i) cin >> value[i] >> weight[i];
// DP初期条件: dp[0][w] = 0
for (ll w = 0; w <= W; ++w) dp[0][w] = 0;
// DPループ
for (ll i = 0; i <= n; ++i) { //荷物の数
for (ll w = 0; w <= W; ++w) { //許容容量
if (w >= weight[i]) dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
else dp[i + 1][w] = dp[i][w]; //最初のみ使用
}
}
cout << dp[n][W] << endl; //n以下 W以下 の最大値
}