Atcorderの高橋くんの苦悩という問題　dpについて

高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、
画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。
画面のスクリーンショットは N枚あり、
高さは全て等しいのですが、幅が異なります。
また、表計算ソフトに貼りつけ可能なスクリーンショットには
2つの制約が存在します。

表計算ソフトの幅は Wしかない。
そのため、貼りつけるスクリーンショットの幅の合計値は
W以下でなければならない。
表計算ソフトは
K枚より多くのスクリーンショットを貼りつけることが出来ない。
よって、表計算ソフトに貼りつけ可能なスクリーンショットは K枚までである。
さらに、スクリーンショットには「重要度」が存在するため、高橋くんは
2つの制約を満たしながら、貼り付けるスクリーンショットが持つ重要度の合計値を最大化したいです。しかし、彼にとってこの仕事は難しいので、あなたが彼の代わりに表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を求めてください。

という問題で、

C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main () {
5  int W,N,K;
6  cin>>W>>N>>K;
7  
8  int a[N+1],b[N+1];
9  for (int i=0;i<N;i++) {
10    cin>>a[i]>>b[i];
11  }
12  int dp[N+1][W+1][K+1]={0};
13  
14
15  for (int i=0;i<N;i++) {
16    for (int j=0;j<=W;j++) {
17      for (int k=1;k<=K;k++) {
18        if (i==0) {
19          dp[i][j][k]=0;
20        }
21        else if (j<a[i]) {
22          dp[i+1][j][k]=max(dp[i][j][k],dp[i+1][j][k]);
23        }
24        else {
25          dp[i+1][j][k]=max(dp[i][j][k],dp[i][j-a[i]][k-1]+b[i]);
26        }
27      }
28    }
29  }
30  int c=-1;
31  for (int k=1;k<=K;k++) {
32    c=max(dp[N][W][k],c);
33  }
34  cout<<c<<endl;  
35}