测试数据来自 system/3048

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H计划用不超过 \(T\) 元钱去珠宝店购买有足够魅力值的宝石。

　　在珠宝店里，提供了 \(N\) 款宝石，其中第 \(i\) 款宝石的价格为 \(v[i]\)，可增加魅力值为 \(w[i]\)。同时有些宝石还搭配有吊坠（最多有两个），当然每个吊坠也有相应的价格 \(tv\) 和可增加的魅力值 \(tw\)。注意，吊坠不能单独购买，只有在其对应的宝石被购买的前提下。

　　请你设计一个程序，帮小H算一下，他该怎么购买宝石，才能使自己的魅力值增加的足够多？

【输入格式】

　　第一行，为两个正整数，用一个空格隔开：\(T,N\)，其中 \(T\) 表示总钱数，\(N\) 为珠宝店提供的宝石款数。
　　接下来的 \(N\) 行，每行表示一款宝石的数据，前两个整数分别是该宝石的价格 \(v[i]\) 和可增加魅力值 \(w[i]\)，第三个数为 \(num\)，表示该款宝石有 \(num\) 个吊坠可配，然后的 \(num\)对整数\(（tv,tw）\)，分别表示一颗吊坠的价格和可增加魅力值。当然 \(num=0\) 时，表示没有可搭配的吊坠。

【输出格式】

　　输出一个正整数，为小H能增加魅力值的最大值。

【输入输出样例】

　Input

100 3
80 160 2 40 200 30 150
40 120 0
50 100 0

　Output

220

【数据限制】

　　\(0<T≤50000\)
　　\(0<N≤100\)
　　\(1≤num≤2\)
　　\(0≤ \)价格\( ≤10000\)
　　\(1≤\) 可增加魅力值\( ≤50000\)

【来源】

　　Mr.he