题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，即每组最多只能选择一件物品。现在，他想知道在背包承重限制下能获得的最大利用价值是多少。

输入格式

第一行两个整数 $m, n$，表示背包能承受的最大重量为 $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 a_i, b_i \le 1000$，$1 \le c_i \le 100$（组别在 $1$ 到 $k$ 之间）