填空题

最佳配置

Question

有一个 的矩形，矩形中的每个点初始值为 ，将每一行都分为若干块，每一块中，最多有一个点可以变化成 ，评判一个矩形质量的计算为：每一列中 的数量的平方和。

例如：一个 的矩形，第一行分成 三块，第二行分成 两块，第三行分成 两块。

那么，下述两种挑点转化成 的方案都是合法的：





而下述方案是不合法的



由于 这个点和 这个点属于同一块，而一块中最多只能出现一个 ，所以不合法。

对于上述两种合法方案而言，第一种方案的矩形质量为：
第二种方案的矩形质量为：

其中，第二种方案的矩形质量是当前分块状态下的最大值，该变化方案称之为最佳配置，显然，最佳配置的方案可能不唯一，但是，同为最佳配置的矩形质量一定是相同且最大的。

那么，对于一种矩形分块的情况，它最佳配置下的矩形质量可以达到多少？ 输入描述： 对于每组测试数据，第一行输入两个正整数 ，代表矩形的行、列长度。

接下去输入 行的分块信息，对于矩形的第 行而言，第一行输入一个正整数 ，代表第 行分成了 块。
接下去 行，每行两个正整数 ，代表第 行的某一分块的起点和终点(闭区间)。

数据保证，每一行的分块区间一定不重叠，且覆盖了 列。输入样例： 3 5 3 1 2 3 4 5 5 2 1 2 3 5 2 1 3 4 5 输出描述： 一行输出一个整数代表某一种最佳配置下的矩形质量。输出样例 19