题目描述

物品分为若干组，每组最多选择一件，求容量限制下最大价值。

输入格式

第一行 V,N,G，随后 N 行重量、价值、组号。

输出格式

输出最大价值。

样例

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

17

数据范围

1≤V≤200，1≤G≤N≤30，1≤物品重量、价值≤10000，1≤组号≤G。每组至少有一件物品。