← 返回题目列表

Codeforces · 1372/E

E. 奥姆卡和最后一层

中文机器翻译题面 查看原题

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$$$。您可以证明没有更高质量的平面图。