#497. 金明的预算方案

金明的预算方案

题目描述

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

0101 背包的基础上,有一些物品有依赖关系。具体来说,若 aa 物品属于 bb 物品,则只有选取 bb 物品后,才能选取 aa 物品。

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

输入格式

第一行两个整数 tottotnn,表示背包大小和物品总件数。

接下来n行,每行有三个数 a,b,ca,b,caa 表示代价,a×ba \times b 表示价值,cc 代表其属于第 cc 个物品。若 cc00,表示它不属于任何物品。

输出格式

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

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

提示

由于 2233 物品属于 11,选了 11 才能选 2233,所以在最优情况下只能选第 4433 个物品。

数据范围

n100n \le 100

tot200000tot \le 200000