Description

A traveler has a backpack that can hold a maximum of V kilograms. There are now n items, with their weights being $W\_1, W\_2, ..., W\_n$ and their values being $C\_1, C\_2, ..., C\_n$, respectively. These items are divided into several groups, and within each group, the items conflict with each other, meaning at most one item can be selected from each group. The task is to determine which items to pack into the backpack so that the total weight does not exceed the backpack's capacity, and the total value is maximized.

Input Format

• First line: Three integers, V (backpack capacity, V ≤ 200), N (number of items, N ≤ 30), and T (maximum group number, T ≤ 10).
• Lines 2 to N+1: Each line contains three integers $W\_i, C\_i, P$, representing the weight, value, and group number of each item, respectively.

Output Format

A single line containing one number, which represents the maximum total value.

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

20