题目描述

有 $n$ 件物品和一个容量为 $m$ 的背包。这些物品被分为若干组，同一组内的物品互相冲突，最多只能选取其中一件。第 $i$ 件物品的重量为 $a_i$，价值为 $b_i$，所属组号为 $c_i$。求在背包容量限制下能获得的最大总价值。

输入格式

第一行两个整数 $m$ 和 $n$，分别表示背包容量和物品总数。

接下来 $n$ 行，每行三个整数 $a_i, b_i, c_i$，依次表示第 $i$ 件物品的重量、价值和所属组号。

输出格式

输出一个整数，表示能获得的最大总价值。

样例

45 3
10 10 1
10 5 1
50 400 2

10

提示

$0 \le m \le 1000$，$1 \le n \le 1000$，$1 \le k \le 100$，$a_i, b_i, c_i$ 在 int 范围内。