1856: 金明的预算方案
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
出题人本来想写个有趣的题面，但是他咕咕咕了太久了，只好简单说明。
在01背包的基础上，有一些物品有依赖关系。具体来说，若a物品属于b物品，则只有选取b物品后，才能选取a物品。
由于出题人太菜了，一个物品最多只有两个附属品，并且其附属品不会再有附属品。
在01背包的基础上，有一些物品有依赖关系。具体来说，若a物品属于b物品，则只有选取b物品后，才能选取a物品。
由于出题人太菜了，一个物品最多只有两个附属品，并且其附属品不会再有附属品。
输入
第一行两个整数tot和n(n≤100,tot≤200,000)，表示背包大小和物品总件数。
接下来n行，每行有三个数a,b,c，a表示代价，a*b表示价值，c代表其属于第c个物品。若c为0，表示它不属于任何物品。
接下来n行，每行有三个数a,b,c，a表示代价，a*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个物品。