【 Input 】

输入文件的第1行，为两个正整数，用一个空格隔开：

N m

（其中N（N< 32000）表示总钱数，m（m< 60）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数

v p q

（其中v表示该物品的价格（v < 10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

【 Output 】

【 Sample Input 】

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

【 Sample Output 】

2200

【 Source/Category 】