Description

After the $01$ knapsack came out, Xiao A became very interested. One day, Xiao A went on a trip and found that his backpack was different from the $01$ knapsack. His items can be roughly divided into $k$ groups, and items within the same group are mutually exclusive (you may choose at most one item from each group). Now he wants to know the maximum total value he can obtain.

Input Format

Two integers $m,n$, indicating there are $n$ items in total, and the backpack can bear a maximum weight of $m$.

Then $n$ lines follow. Each line contains 3 integers $a_i,b_i,c_i$, representing the item's weight, value, and group index.

Output Format

One integer: the maximum total value.

45 3
10 10 1
10 5 1
50 400 2

10

Hint

$0 \leq m \leq 1000$, $1 \leq n \leq 1000$, $1\leq k\leq 100$, $a_i, b_i, c_i$ are within the int range.

Translated by ChatGPT 5