题目描述

将 $n$ 件物品放入一个容量为 $V$ 的背包，其中第 $i$ 件物品的体积为 $c_i$，价值为 $v_i$；同时，和01背包问题不同的是，本题中还有一个限制，就是每件物品都有一个分组，第 $i$ 件物品属于第 $g_i$ 个分组。同一个分组中最多只能选择一件物品放入背包中。

举个例子：如果有两件物品（设为物品 $A$ 和 物品 $B$）都属于同一个分组，则要么选择物品 $A$，要么选择物品 $B$，要么都不选择（即满足 “同一个分组中最多只能选择一件物品放入背包中” 的条件）

求：在满足上述条件且物品体积之和不超过背包容量 $V$ 的情况下能够放入背包当中的物品价值之和的最大值。

输入格式

输入的第一行包含两个整数 $V$ 和 $n$，以一个空格分隔，分别表示背包体积与物品数量。（$1 \le V,n \le 1000$）
接下来 $n$ 行，每行包含三个整数，两两之间以一个空格分隔，其中第 $i$ 行包含的三个整数 $c_i, v_i, g_i$ 分别表示第 $i$ 件物品的体积、价值和分组。（$1 \le c_i,v_i,g_i \le 1000$）

输出格式

输出一个整数，表示在满足分组条件限制且物品体积之和不超过背包容量 $V$ 的情况下能够放入背包当中的物品价值之和的最大值。

样例

45 3
10 10 1
10 5 1
50 400 2

10