题目描述

小明搬进了新家，妈妈给了他一笔不超过 $n$ 元的预算，让他自行采购物品布置房间。

小明需要购买的物品分为主件和附件两类。附件必须依附于某个主件——要买某个附件，就必须同时购买它所属的主件。每个主件最多有 $2$ 个附件，附件自身不再附带其他附件。

小明把每件物品按重要程度分为 $1$ 到 $5$ 共五个等级（$5$ 最重要），并查到了每件物品的价格（均为 $10$ 的整数倍）。他希望在预算范围内，使所选物品的「价格 $\times$ 重要度」之和最大。

设选中了 $k$ 件物品，编号依次为 $j_1, j_2, \ldots, j_k$，则目标值为：

$$v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \cdots + v_{j_k} \times w_{j_k}$$

其中 $v_j$ 为第 $j$ 件物品的价格，$w_j$ 为其重要度。请你帮小明选出一个最优方案。

输入格式

第一行两个整数 $n, m$，分别表示总预算和物品总数。

接下来 $m$ 行，第 $i+1$ 行三个整数 $v_i, w_i, q_i$，分别表示第 $i$ 件物品的价格、重要度和所属主件编号。$q_i = 0$ 表示该物品本身是主件。

输出格式

输出一行一个整数，表示答案。

样例

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200

提示

数据规模

$1 \le n \le 3.2 \times 10^4$，$1 \le m \le 60$，$0 \le v_i \le 10^4$，$1 \le w_i \le 5$，$0 \le q_i \le m$，答案不超过 $2 \times 10^5$。