Migrated from Lutece 2583 种蘑菇

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你是提莫，可能是召唤师峡谷中最可爱的生物。你有一个技能是种蘑菇，在一个地方放下一个蘑菇，如果敌人经过就会爆炸造成伤害。

这一次，你又准备把蘑菇种满峡谷。

形象地讲，我们可以把召唤师峡谷看成一个棋盘，有 $n$ 行 $m$ 列。

行与行之间在我们划分的时候本身就是分割的，但一行中的各列是连在一起的，不过由于峡谷中的岩石和山丘的存在，一行被分割开了成了多个间隔，也可能不分割。

而你想要让敌人尽可能多地踩到蘑菇，但蘑菇的生成有冷却时间，所以不能每个地方都放，于是你打算在每行中的每个间隔内都放且只放一个蘑菇。

把 $n$ 行 $m$ 列看成棋盘，则每行每列都可能放一个蘑菇，那么可以视为有 $n\times m$ 个单位。

最后你要给出最优布局下的最高蘑菇伤害得分。

蘑菇伤害得分的计算方法就是计算各列的蘑菇伤害得分，一列的蘑菇伤害得分等于该列的蘑菇数的平方。

比如现在召唤师峡谷有 $3$ 行，$10$ 列，每行的间隔划分是

• 第一行，两个间隔：$1-5,6-10$
• 第二行，一个间隔：$1-10$
• 第二行，一个间隔：$1-10$

则其中一种最优方案就是每行的第一个间隔都放第一个位置，第一行的第二个间隔随便放一个位置，则最高蘑菇伤害得分就是 $3\times 3+1\times 1=10$ 。

Input

第一行是两个整数 $n,m\ (1\le n,m\le 100)$ 分别代表召唤师峡谷棋盘的行数和列数。

接下来 $n$ 行描述每行间隔的情况，首先是一行一个整数 $k\ (1\le k\le m)$ 代表这一行的间隔数，接下来 $k$ 行每行两个整数 $s,t\ (1\le s\le t\le m)$，分别代表这个间隔最左边的列号和最右边的列号。输入保证一行的间隔划分是合法的，即无重叠、长度至少为 $1$。

Output

一行一个整数，代表最优布局下的最高蘑菇伤害得分。

Samples

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

Note

样例的最优方案就是第一行放 $1$ 和 $5$，第二行放 $1$ 和 $5$，第三行放 $1,2,5$，第 $4$ 行放 $1,2,5$。答案就是 $4\times 4+2\times 2+4\times 4=36$。

Resources

2021 UESTC ICPC Training for Dynamic Programming