说明

自 $01$ 背包问世之后，小 $A$ 对此深感兴趣。一天，小 $A$ 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突(即每个小组中至多选一件物品)，现在，他想知道在不超过背包容量为$m$ 的情况下,能过去的最大价值是多少。

输入格式

第一行输入两个正整数 $m,n$，分别表示背包最大承重量和物品的数量。

接下来 $n$ 行，每行 $3$ 个数 $w_i,v_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的价值。

45 3
10 10 1
10 5 1
50 400 2

10

##【样例 1 解释】 第一小组有 $2$ 件物品组成,选择了一件重量为$10$,价值为$10$的物品 第二小组由 $1$ 件物品组成,一件物品都不选择。 能证明此方案为最优方案

提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$w_i, v_i, k_i$ 在 int 范围内。