最后一层楼

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一个初始全为零的 $n\times m$ 矩阵。每一行都被划分为若干个互不重叠、首尾相接并覆盖整行的区间。

对每行的每个区间，必须恰好选择其中一个位置，把该位置改成 $1$。设第 $j$ 列中 $1$ 的数量为 $q_j$，矩阵的质量为

求可能得到的最大质量。

输入格式

第一行两个整数 $n,m$。

随后依次描述每一行。先输入该行的区间数 $k_i$，再输入 $k_i$ 行，每行两个整数 $l,r$。输入保证这些区间按顺序首尾相接，并恰好覆盖 $[1,m]$。

输出格式

输出最大质量。

样例输入

4 5
2
1 2
3 5
2
1 3
4 5
3
1 1
2 4
5 5
3
1 1
2 2
3 5

样例输出

36

数据范围

$1\le n,m\le100$。

每个测试点独立计分。