给定 n 个序列 {a1,i},{a2,i},…,{an,i},第 i 个序列长度为 mi,每个序列的每个元素都是 0 到 2×106 之间的整数。定义 ai 的后继是 ai+1(1≤i≤n−1),而 an 的后继是 a1。ai 的后继记作 succ(i)。
定义一个序列的代价为,向序列中加入一个 0 和一个 2×106,排序后,相邻两个数差的平方之和。即若排序后是 0=p0≤p1≤p2≤⋯≤pk−1≤pk=2×106,那么代价为 ∑k−1i=0(pi+1−pi)2。
定义一个分割为整数序列 x1,x2,…,xn,满足 1≤xi≤mi。
定义第 i 个分割后的序列是由 ai 的 [xi,mi] 号元素,加上 asucc(i) 的 [1,xsucc(i)−1] 号元素组成的序列。定义一个分割的代价是所有 n 个分割后的序列的代价之和。
求代价最小的分割。输出最小代价的值即可。
输入格式
第一行一个整数 n。
接下来 n 行,每行包含一个整数 mi 和 mi 个整数 ai,1,…,ai,mi。
输出格式
一行一个整数表示最小代价。
样例
样例输入 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
数据范围与约定
记 ∑m 表示所有序列的长度之和。
对于所有数据,n≥2,mi≥2,∑m≤2×105,0≤ai,j≤2×106。
- Subtask1(10pts):∑m≤100;
- Subtask2(20pts):∑m≤1000;
- Subtask3(30pts):∑m≤5×104;
- Subtask4(40pts):∑m≤2×105;