Given $n$ sequences $\{a_{1, i}\}, \{a_{2, i}\}, \dots, \{a_{n, i}\}$, where the $i$-th sequence has length $m_i$, and each element in every sequence is an integer between $0$ and $2 \times 10^6$. The successor of $a_i$ is defined as $a_{i+1}$ (for $1 \leq i \leq n-1$), and the successor of $a_n$ is $a_1$. The successor of $a_i$ is denoted as $succ(i)$.

The cost of a sequence is defined as follows: add one $0$ and one $2 \times 10^6$ to the sequence, sort the resulting sequence, and calculate the sum of the squares of the differences between adjacent elements. That is, if the sorted sequence is $0 = p_0 \leq p_1 \leq p_2 \leq \dots \leq p_{k-1} \leq p_k = 2 \times 10^6$, the cost is $\sum_{i=0}^{k-1}(p_{i+1} - p_i)^2$.

A partition is defined as a sequence of integers $x_1, x_2, \dots, x_n$ such that $1 \leq x_i \leq m_i$.

The $i$-th partitioned sequence is formed by the elements of $a_i$ from index $x_i$ to $m_i$, combined with the elements of $a_{succ(i)}$ from index $1$ to $x_{succ(i)} - 1$. The cost of a partition is the sum of the costs of all $n$ partitioned sequences.

Find the partition that minimizes the total cost. Output the minimum cost.

Input

The first line contains an integer $n$.

The next $n$ lines each contain an integer $m_i$ followed by $m_i$ integers $a_{i, 1}, \dots, a_{i, m_i}$.

Output

Output a single integer representing the minimum cost.

Examples

Input 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

Output 1

4522800735482

Constraints

Let $\sum m$ denote the sum of the lengths of all sequences.

For all test cases, $n \geq 2, m_i \geq 2, \sum m \leq 2 \times 10^5, 0 \leq a_{i, j} \leq 2 \times 10^6$.

• Subtask 1 (10 pts): $\sum m \leq 100$
• Subtask 2 (20 pts): $\sum m \leq 1000$
• Subtask 3 (30 pts): $\sum m \leq 5 \times 10^4$
• Subtask 4 (40 pts): $\sum m \leq 2 \times 10^5$