Omkar 正在建造一座房子。他想决定如何制定最后一层的平面图。
Omkar 的地板一开始是 $$$n$$$ 行 $$$m$$$ 零 ($$$1 \le n,m \le 100$$$)。每行都分为多个区间,使得该行中的每个 $$$0$$$ 恰好位于 $$$1$$$ 区间内。对于每一行的每个间隔,Omkar 可以将该间隔中包含的 $$$0$$$ 之一精确地更改为 $$$1$$$。 Omkar 将楼层质量定义为每列 i 中值总和的平方和。 e.如果第 $$$i$$$ 列中的值的总和为 $$$q_i$$$,则地板的质量为 $$$\sum_{i = 1}^m q_i^2$$$。
帮助 Omkar 找到地板可以达到的最高质量。
输入
第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 100$$$),分别是行数和列数。
然后,您将收到每行间隔的说明。对于从 $$$1$$$ 到 $$$n$$$ 的每一行 $$$i$$$:第一行包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le m$$$),它是行 $$$i$$$ 上的间隔数。接下来的 $$$k_i$$$ 行的第 $$$j$$$ 行包含两个整数 $$$l_{i,j}$$$ 和 $$$r_{i,j}$$$,它们分别是第 $$$i$$$ 行的第 $$$j$$$ 区间的左边界和右边界(包括两者)。确保除第一个间隔之外的所有间隔都将直接位于其之前的间隔之后。形式上,$$$l_{i,1} = 1$$$,$$$l_{i,j} \leq r_{i,j}$$$ 对于所有 $$$1 \le j \le k_i$$$,$$$r_{i,j-1} + 1 = l_{i,j}$$$ 对于所有 $$$2 \le j \le k_i$$$,并且$$$r_{i,k_i} = m$$$。
输出
输出一个整数,这是合格平面图的最大可能质量。
示例
输入 #1
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
输出 #1
36
注意
给定的测试用例对应于下图。同一行中具有相同编号的单元格属于同一区间的一部分。
最佳分配是:
第 $$$1$$$st 列的总和为 $$$4$$$,第 $$$2$$$nd 列的总和为 $$$2$$$,第 $$$3$$$rd 和第 $$$4$$$ 列的总和为 $$$0$$$,第 $$$5$$$ 列的总和为 $$$4$$$。
该平面图的质量为 $$$4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$$$。您可以证明没有更高质量的平面图。