解法
ナップザック問題の DPと同じで，部分和問題の DP. 状態数が少ない様に DP の定義域と値域を選ぶと， 空間計算量と時間計算量が小さくできる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll w; cin >> w;
ll n,k;
cin >> n >> k;
vll a(n), b(n);
rep(i,n){
cin >> a[i] >> b[i];
}
const ll c = n * 100 + 5;
vvll dp(c+1, vll(k+1, INFL)); // WA: init 1000*n + 5
dp[0][0] = 0;
rep(i,n) {
drep(ki,k) drep(x,c+1){
if(x + b[i] <= c) chmin(dp[x + b[i]][ki+1], dp[x][ki] + a[i]);
}
}
ll ans = 0;
drep(x,c+1) rep(ki,k+1){
if(dp[x][ki] <= w){
chmax(ans, x);
}
}
cout << ans << endl;
return 0;
}
