给定 $n$ 个序列 $\{a_{1, i}\}, \{a_{2, i}\}, \dots, \{a_{n, i}\}$，第 $i$ 个序列长度为 $m_i$，每个序列的每个元素都是 0 到 $2 \times 10^6$ 之间的整数。定义 $a_i$ 的后继是 $a_{i+1}$（$1\leq i\leq n-1$），而 $a_n$ 的后继是 $a_1$。$a_i$ 的后继记作 $succ(i)$。

定义一个序列的代价为，向序列中加入一个 0 和一个 $2 \times 10^6$，排序后，相邻两个数差的平方之和。即若排序后是 $0 = p_0\leq p_1\leq p_2\leq \dots\leq p_{k-1}\leq p_k = 2\times 10^6$，那么代价为 $\sum_{i=0}^{k-1}(p_{i+1} - p_i) ^ 2$。

定义一个分割为整数序列 $x_1, x_2, \dots, x_n$，满足 $1 \leq x_i \leq m_i$。

定义第 $i$ 个分割后的序列是由 $a_i$ 的 $[x_i, m_i]$ 号元素，加上 $a_{succ(i)}$ 的 $[1, x_{succ(i)} - 1]$ 号元素组成的序列。定义一个分割的代价是所有 $n$ 个分割后的序列的代价之和。

求代价最小的分割。输出最小代价的值即可。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行包含一个整数 $m_i$ 和 $m_i$ 个整数 $a_{i, 1}, \dots, a_{i, m_i}$。

输出格式

一行一个整数表示最小代价。

样例

样例输入 1

4
5 414276 935411 204664 302847 1142143
5 162307 1199651 1168780 39659 991911
6 1204312 442315 639803 28852 1019073 143732
4 279750 1185347 612942 1086837

样例输出 1

4522800735482

数据范围与约定

记 $\sum m$ 表示所有序列的长度之和。

对于所有数据，$n\geq 2, m_i \geq 2, \sum m \leq 2\times 10^5, 0\leq a_{i, j} \leq 2\times 10^6$。

• Subtask1（10pts）：$\sum m \leq 100$；
• Subtask2（20pts）：$\sum m \leq 1000$；
• Subtask3（30pts）：$\sum m \leq 5\times 10^4$；
• Subtask4（40pts）：$\sum m \leq 2\times 10^5$；