题目描述

出题人本来想写个有趣的题面，但是他咕咕咕了太久了，只好简单说明。

在 $01$ 背包的基础上，有一些物品有依赖关系。具体来说，若 $a$ 物品属于 $b$ 物品，则只有选取 $b$ 物品后，才能选取 $a$ 物品。

由于出题人太菜了，一个物品最多只有两个附属品，并且其附属品不会再有附属品。

输入格式

第一行两个整数 $tot$ 和 $n$，表示背包大小和物品总件数。

接下来n行，每行有三个数 $a,b,c$，$a$ 表示代价，$a \times b$ 表示价值，$c$ 代表其属于第 $c$ 个物品。若 $c$ 为 $0$，表示它不属于任何物品。

输出格式

一个整数，表示最优的答案。

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

2200

提示

由于 $2$、$3$ 物品属于 $1$，选了 $1$ 才能选 $2$、$3$，所以在最优情况下只能选第 $4$、$3$ 个物品。

数据范围

$n \le 100$

$tot \le 200000$