题目描述
大聪明需要快速地补充能量，小极客从艾达空间取出了一些能量棒帮助大聪明恢复能量。
但是大聪明的手臂能安装的体积是有限的，每只能量棒的体积和单位能量也是不同的。每只能量棒能恢复的总能量等于他的体积乘以他的单位能量。
这些能量棒分为核心能量棒和辅助能量棒。红色的是核心能量棒，蓝色的是辅助能量棒。每个核心能量棒可以单独使用，每个辅助能量棒都有对应的一个核心能量棒，只有使用了这个辅助能量棒对应的核心能量棒，才能使用它对应的辅助能量棒。而且在这些能量棒中，每个核心能量棒可能没有对应的辅助能量棒，也可以有一个辅助能量棒或者两个辅助能量棒，但一定不会有超过两个以上的辅助能量棒数量。
大聪明想在使用这些能量棒前，先对这些能量棒进行整理，把每个辅助能量棒放在它对应的核心能量棒后，并计算出每个能量棒的总能量。
请你帮助大聪明完成这个题目。
输入
第一行有两个整数，n和m分别代表大聪明机械手臂能装的最大体积，和能量棒的总数。(1 <= n <= 32000, 1 <= m <= 60)
第2到第(m + 1)行，每行三个整数，第(i+1)行的整数vi,pi,qi分别表示第i件能量棒的体积、单位价值以及它对应的的核心能量棒。如果qi=0表示该物品本身是核心能量棒。(0 <= vi <= 10000, 1 <= pi <= 5, 0 <= qi <= m)
输出
输出一行一个整数表示大聪明能恢复的最大能量。
样例输入
10 5
8 2 0
3 5 1
4 3 0
5 2 0
4 5 1样例输出
22