说明

大恺每天呆在寝室里钻研算法知识，终于到了五一假期，他可以快乐地出门购物了。

在购物前，他有一个总的花费预算N，表示他总共花费不能超过N。

同时他有一个想要购买的商品清单，M表示他清单中的商品个数(不包括附属商品)。

来到超市后，他发现他想买的每一个商品都有0~2个附属商品，如果想要购买这些附属商品，一定要先购买所属的原商品。（例如——若商品“篮球”包含两个附属商品：“打气筒”和“篮球袋”，那么大恺可以选择只购买一个篮球；购买篮球加打气筒；购买篮球加篮球袋；或者是把篮球、打气筒和篮球袋全买下来；当然，也可以不买篮球及其附属商品。但是，不可以只买打气筒或篮球袋）

在逛了一圈后，大恺对每一个商品（包括附属商品）都有一个满意度，现在请你帮他算一算，如何在不超过预算的情况下，购买到的商品满意度总和最大。

输入格式

输入数据包括M + 1行

第一行包括两个整数N，M，分别表示大恺的总花费预算和愿望清单中商品的数量（不包括附属商品）

接下来的M行，每行的前三个数v, p, q分别表示当前商品的价钱，满意度以及该商品的附属商品数量

每行接下来包括2 * q个数，依次表示当前商品附属商品的价钱和满意度

输出格式

输出一个正整数，表示不超过预算限制下，大恺可以获得的最大满意度

样例

1000 3
800 5 0
300 1 1 200 2
400 2 2 100 1 200 1

6

提示

数据范围: (1 <= N <= 50000, 1 <= M <= 50, 1 <= v <= 1000, 0 <= p <= 10, 0 <= q <= 2)