[HNOI2006]军机调度

凯萨拥有一支由 $n$ 名雇佣军组成的军队，他们依靠接受威尼斯商行发布的任务维持生计。军队成员拥有不同的技能，有些人还掌握多项技能，因此每个人能够执行的任务可能不同。

威尼斯商行提供的任务各不相同。有些任务需要多人合作完成，有些任务只需一人独立完成；任务的难度、持续时间和报酬也各有差异。所有任务都能在一个月内完成。

一名雇佣军不能同时执行两项任务，也不能在任务进行途中加入或退出，但可以不执行任何任务。

对于一项原本需要 $p$ 人完成的任务，如果实际安排了 $q$ 人且 $q>p$，则该任务的报酬将降低为原报酬的

$$\frac{1}{q-p+1}。$$

凯萨会在每个月月底召开军事会议，总结上个月的成果、发放报酬，并安排下个月的任务。请你帮助凯萨制定任务分配方案，使获得的总报酬最大，并求出最大总报酬。

输入格式

第一行包含两个正整数 $n,m$，分别表示雇佣军人数和下个月可选的任务数，整数之间以空格分隔。

接下来 $n$ 行描述每名雇佣军能够执行的任务。第 $i$ 行的第一个整数表示编号为 $i$ 的雇佣军能够执行的任务数，后面的整数依次表示这些任务的编号，整数之间以空格分隔。

最后 $m$ 行描述各项任务。第 $j$ 行包含四个整数 $b,e,p,r$，表示编号为 $j$ 的任务：

• $b$ 表示任务的开始日期，开始当天计入任务持续时间；
• $e$ 表示任务的结束日期，结束当天也计入任务持续时间；
• $p$ 表示该任务所需的人数；
• $r$ 表示该任务的原始报酬。

同一行中的整数以空格分隔。

输出格式

输出一行一个整数 $t$，表示最多可以获得的总报酬。

样例输入

3 5
2 1 4
2 2 4
3 3 4 5
2 20 1 100
1 18 1 200
3 28 1 800
21 30 3 1500
19 21 1 400

样例输出

1800

数据范围

• $n<10$，$m<15$；
• $0<b<32$，$0<e<32$；
• $p<10$；
• $0<r<10^5$；
• 时间限制：$10000\ \mathrm{ms}$；
• 内存限制：$165888\ \mathrm{KB}$。

来源与许可

本题为 HNOI 2006 试题「军机调度」，题面与测试数据整理自 BZOJ 1198。

样例 1

输入

3 5
2 1 4
2 2 4
3 3 4 5
2 20 1 100
1 18 1 200
3 28 1 800
21 30 3 1500
19 21 1 400

输出

1800