题目大意：有n个物品，有主件有附件，主件买了其对应的附件才能购买，每个物品的价值为价格*重要度，给你m元，能获得的最大价值是多少？
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
| 电脑 | 打印机 |
| 扫描仪 | 书柜 |
| 图书 | 书桌 |
| 台灯 | 文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1*w[j1+v[j2*w[j2+ …+v[jk*w[jk。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
输入
输入文件的第1行，为两个正整数，用一个空格隔开：
N m 其中N（< 32000）表示总钱数，m（< 60）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数
v p q （其中v表示该物品的价格（v< 10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q> 0，表示该物品为附件，q是所属主件的编号）
输出
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （< 200000）。
样例输入
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出
2200
提示
NOIP2006提高组第二题
解题思路
由于最多只有2个附件，所以每一类物品可以拆分成最多4个物品，即只选主件，选主件和任意附件，选2个附件。分好类后，跑一遍分组背包即可。
如果不会分组背包，或者嫌麻烦，可以用爆搜，因为数据范围比较小。
程序实现
爆搜60分：暴力枚举每一种物品选不选，枚举完后，检查一下是否存在选了附件没选主件的情况，如果没有这种异常情况，那么记录最优值。时间复杂度O(2^n * n)。
排序优化70分：按照q排序，主件q=0排在前面，可以保证主件先选完再选附件。这样选附件的时候，就可以直接判断是否可以选择。时间复杂度O(2^n)。
记忆化剪枝满分：开一个数组f[k][x]表示选到第k个物品，花费为x的最大价值。对于k是主件进行记忆化，因为此时剩下的物品是k到n，不受前面影响，价值固定，如果前面出现重复或者更差的情况，就没必要搜下去。
