题目描述

NOIP 2006

张琪曼等人要为太空战指挥中心购置设备，魔法学院的院长昨天说:"指 挥中心需要购买哪些设备，你们研究了算,只要不超过$\red{N}$元钱就行"。所以今天一 早,张琪曼就开始做预算了,她把想买的物品分为两类:主件与附件，附件是从属 于某个主件的，表中就是一些主件与附件的例子:

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 $\red{0}$个、$\red{1}$个或$\red{2}$个附件。附件不再有从属于自己的附件。指挥中心想配备的东西很 多,肯定会超过院长限定的$\red{N}$元。于是，她把每件物品规定了一个重要度，分为$\red{5}$ 等:用整数$\red{1\sim 5}$表示，第$\red{5}$等最重要。她还从互联网上查到了每件物品的价格 $\red{(}$都是$\red{10}$元的整数倍$\red{)}$。她希望在不超过$\red{N}$元$\red{(}$可以等于$\red{N}$元$\red{)}$的前提下，使每件 物品的价格与重要度的乘积的总和最大。 设第$\red{j}$件物品的价格为$\red{v[j],}$重要度为$\red{w[j],}$共选中了$\red{k}$件物品，编号依次为 $\red{j1,j2,...,jk,}$则所求的总和为: $\red{v[j1]\times w[j1]+v[j2]\times w[j2]+...+ v[jk]\times w[jk]}$。

请你帮助张琪曼设计一个满足要求的购物单。

输入格式

第$\red{1}$行为两个正整数,用一个空格隔开: $\red{N }$$\red{~m}$(其中 $\red{N(<32 000)}$表示总钱数， $\red{m(<60)}$为希望购买物品的个数)。 从第$\red{2}$行到第$\red{m+1}$行,第$\red{j}$行给出了编号为$\red{j-1}$的物品的基本数据,每行有 $\red{3}$个非负整数$\red{v ~p ~q}$(其中$\red{v}$表示该物品的价格$\red{(v<10000),p}$表示该物品的重 要度$\red{(1\sim5),q}$表示该物品是主件还是附件。如果$\red{q=0,}$表示该物品为主件,如果 $\red{q>0,}$表示该物品为附件,$\red{q}$是所属主件的编号)。

输出格式

输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的 最大值$\red{(<200 000)}$。

样例

输入样例

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

输出样例

2200