まず，物を色の昇順にソートしておきます．（色以外のキーの順番は不問です）

このとき，\(dp[i][j][k][l] =\) (\(i\) 番目のものまでを選ぶか選ばないかを決めたとき，選んだものの重さの合計が \(j\) であり，選んだものの色の種類数が \(k\) である選び方における，価値の合計の最大．ただし，\(l = 0\) のとき \(i\) 番目のものと色が同じものを選んでおらず，\(l = 1\) のとき \(i\) 番目のものと色が同じものを選んでいる) という DP を考えます．

遷移は \(i\) 番目のものの色と \(i + 1\) 番目のものの色が等しいかどうかに応じて変化します．より具体的には

• \(C_i = C_{i + 1}\) の場合
  • \(i + 1\) 番目のものを選ぶことに決めた場合は \(dp[i + 1][*][k][1] \leftarrow dp[i][*][k][1], dp[i + 1][*][k + 1][1] \leftarrow dp[i][*][k][0]\) という遷移を行う．
  • \(i + 1\) 番目のものを選ばないことに決めた場合は \(dp[i + 1][*][k][1] \leftarrow dp[i][*][k][1], dp[i + 1][*][k + 1][0] \leftarrow dp[i][*][k][0]\) という遷移を行う．
• \(C_i \neq C_{i+1}\) の場合
  • \(i + 1\) 番目のものを選ぶことに決めた場合は \(dp[i + 1][*][k + 1][1] \leftarrow dp[i][*][k][1], dp[i + 1][*][k + 1][1] \leftarrow dp[i][*][k][0]\) という遷移を行う．
  • \(i + 1\) 番目のものを選ばないことに決めた場合は \(dp[i + 1][*][k][0] \leftarrow dp[i][*][k][1], dp[i + 1][*][k + 1][0] \leftarrow dp[i][*][k][0]\) という遷移を行う．

\(\max_{0 \leq w \leq W, 0 \leq c \leq C, 0 \leq l \leq 1} dp[N][w][c][l] \) が答えです．状態数が \(O(NWC)\)，遷移が \(O(1)\) なのでこの DP は \(O(NWC)\) で計算可能です．