测试数据来自 wjszez/1676

【题目背景】
yk真的很喜欢吃，这点大家都知道~
不过，他不光喜欢吃糖果，还喜欢吃馒头，吃包子，吃玉米，吃南瓜，吃花生……yk
喜欢吃这么多东西，并且为了一次吃过瘾，他还发明了玉米馒头，南瓜馒头，花生
馒头……白馒头馅的包子，玉米馒头馅的包子，南瓜馒头馅的包子，花生馒头馅的包
子，玉米南瓜馒头馅的包子……后来，一个包子就变成了一个无敌巨无霸，中间塞了
玉米馒头、南瓜馒头、玉米南瓜馒头、南瓜花生馒头包子……包子里面塞馒头，包子
里面塞包子…… yk看着这些超级无敌巨无霸，心里真的好欢畅啊好欢畅~ 有这么多
好吃的~ yummy~
【问题描述】
现在yk身边只有N种馒头包子，包子里面包的可能是馒头也可能还是是包子 -_-||
每种包子有一个填饱程度c[i]，yk的肚子只有M那么大，也就是yk吃的所有馒头包
子的填饱程度和不能大于M。每种包子还有一个美味程度系数v[i]，则一个包子的
满足度为v[i]*c[i]，yk想在不撑坏肚子的情况下得到最大的满足度。可是有的馒头虽然好吃，但是却是包在某个包子里面的，如果yk想吃到这个馒头，必须先吃掉
这个包子皮，不过好在包子皮里面最多只有两种馅，这样yk就不用担心包子太大吃
不下啦~ 现在yk想知道在满足上述所有条件的情况下，他最多能得到多少满足度。
【输入格式】
dumpling.in
第一行两个用空格隔开的正整数，M，N，分别表示yk肚子的大小和馒头馅的包子数
目
下面N行，每行3个整数c,v,k
第i+1行的三个整数c[i], v[i], k[i]，c[i]表示馒头包子的填饱程度，v[i]
表示美味程度系数，k[i]=0表示你可以直接吃掉这个包子，否则k[i]表示如果要
吃这个馒头必须先吃掉第k[i]个包子的包子皮（一个包子皮里面最多包两种馅）
【输出格式】
dumpling.out
一行一个正整数，表示yk在不撑坏的情怀下最多能得到的满足度。
【样例】
dumpling.in
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
dumpling.out
2200
【数据范围】
100% M<32000, N<60, c<10000, v<6。保证答案不超过 200000