2103: 馒头馅的包子

yk真的很喜欢吃，这点大家都知道~
不过，他不光喜欢吃糖果，还喜欢吃馒头，吃包子，吃玉米，吃南瓜，吃花生……yk喜欢吃这么多东西，并且为了一次吃过瘾，他还发明了玉米馒头，南瓜馒头，花生馒头……白馒头馅的包子，玉米馒头馅的包子，南瓜馒头馅的包子，花生馒头馅的包子，玉米南瓜馒头馅的包子……后来，一个包子就变成了一个无敌巨无霸，中间塞了玉米馒头、南瓜馒头、玉米南瓜馒头、南瓜花生馒头包子……包子里面塞馒头，包子里面塞包子…… yk看着这些超级无敌巨无霸，心里真的好欢畅啊好欢畅~ 有这么多好吃的~ yummy~

现在yk身边只有N种馒头包子，包子里面包的可能是馒头也可能还是是包子 -_-|| 每种包子有一个填饱程度c[i]，yk的肚子只有M那么大，也就是yk吃的所有馒头包子的填饱程度和不能大于M。每种包子还有一个美味程度系数v[i]，则一个包子的满足度为v[i]*c[i]，yk想在不撑坏肚子的情况下得到最大的满足度。可是有的馒头虽然好吃，但是却是包在某个包子里面的，如果yk想吃到这个馒头，必须先吃掉这个包子皮，不过好在包子皮里面最多只有两种馅，这样yk就不用担心包子太大吃不下啦~ 现在yk想知道在满足上述所有条件的情况下，他最多能得到多少满足度。

第一行两个用空格隔开的正整数，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]个包子的包子皮（一个包子皮里面最多包两种馅）

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

2200