曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

2422: 金明的预算方案

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：142 Solved：0
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

出题人本来想写个有趣的题面，但是他咕咕咕了太久了，只好简单说明。 
在01背包的基础上，有一些物品有依赖关系。具体来说，若a物品属于b物品，则只有选取b物品后，才能选取a物品。 
由于出题人太菜了，一个物品最多只有两个附属品，并且其附属品不会再有附属品。 

Input

第一行两个整数tot和n(n≤100,tot≤200,000)，表示背包大小和物品总件数。 
接下来n行，每行有三个数a,b,c，a表示代价，a*b表示价值，c代表其属于第c个物品。若c为0，表示它不属于任何物品。 

Output

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

Sample Input Copy 

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

Sample Output Copy 

2200

HINT

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

Source/Category