H - ナップザック
解説
/
N 個の物があり、i 番目のものの重さ、価値、色はそれぞれw_i, v_i, c_i である。すぬけ君は、いくつかのものをナップザックに入れることにした。ただし、ナップザックに入れるものの重さの合計は W 以下であり、色は C 種類以下でなければならない。ナップザックに入れられるものの価値の合計の最大値を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
二番目と三番目のものを入れるとよい。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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