Grouped Knapsack

Background

Special for beginners, ^_^

Problem Description

A traveler has a knapsack that can hold at most $V$ kilograms. Now there are $n$ items with weights $W_1, W_2, \dots, W_n$ and values $C_1, C_2, \dots, C_n$. The items are divided into several groups; the items within the same group conflict with each other, so at most one item from each group may be chosen. Solve which items to put into the knapsack so that the total cost does not exceed the knapsack capacity and the total value is maximized.

Input Format

The first line has three integers, $V$ (knapsack capacity, $V \le 200$), $N$ (number of items, $N \le 30$), and $T$ (the largest group number, $T \le 10$).

Lines $2 \dots N+1$: each line has three integers $W_i, C_i, P_i$, denoting the weight, value, and group number of each item.

Output Format

A single line with one number: the maximum total value.

Sample Input 1

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

Sample Output 1

20

Constraints

1s, 1024KiB for each test case.