题目描述

你有$\red n$张邮票，编号分别从$\red {0..n-1}$，同时，你有m个客户，每个客户会要求购买$\red 1$或者$\red 2$张邮票，一个客户只有所有的邮票都被满足，才会支付给你报酬。

每张邮票最多被两个客户预定。

要求你指定方案使得获利最大。

输入格式

第一行两个数$\red n$，$\red m$ 以下$\red m$行，每行第一个数$\red t$，表示预定的邮票个数，之后$\red t$个数，最后一个数$\red c$，表示报酬。

输出格式

一个数最大获利

样例

输入样例

3 3
2 0 1 10
2 0 2 11
2 1 2 12

输出样例

12

数据规模 $\red{30\% m<=20}$ $\red{100\% n,m<=50}$