H - ナップザック Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個の物があり、i 番目のものの重さ、価値、色はそれぞれw_i, v_i, c_i である。すぬけ君は、いくつかのものをナップザックに入れることにした。ただし、ナップザックに入れるものの重さの合計は W 以下であり、色は C 種類以下でなければならない。ナップザックに入れられるものの価値の合計の最大値を求めよ。

Constraints

  • 1 ≤ N ≤100
  • 1 ≤ W ≤10000
  • 1 ≤ C ≤ 50
  • 1 ≤ w_i, v_i ≤ 10000
  • 1 ≤ c_i ≤ 50

Input Format

入力は以下の形式で標準入力から与えられる。
N W C
w_1 v_1 c_1
…
w_N v_N c_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4 5 2
1 10 1
1 20 2
1 30 3
10 100 4

Sample Output 1

50
二番目と三番目のものを入れるとよい。

Sample Input 2

10 20 2
4 5 6
3 3 9
5 2 9
4 1 6
6 8 3
3 7 6
2 4 9
4 7 3
6 5 6
3 2 9

Sample Output 2

27