QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[+15]
统计

给定 n 个序列 {a1,i},{a2,i},,{an,i},第 i 个序列长度为 mi,每个序列的每个元素都是 0 到 2×106 之间的整数。定义 ai 的后继是 ai+11in1),而 an 的后继是 a1ai 的后继记作 succ(i)

定义一个序列的代价为,向序列中加入一个 0 和一个 2×106,排序后,相邻两个数差的平方之和。即若排序后是 0=p0p1p2pk1pk=2×106,那么代价为 k1i=0(pi+1pi)2

定义一个分割为整数序列 x1,x2,,xn,满足 1ximi

定义第 i 个分割后的序列是由 ai[xi,mi] 号元素,加上 asucc(i)[1,xsucc(i)1] 号元素组成的序列。定义一个分割的代价是所有 n 个分割后的序列的代价之和。

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

输入格式

第一行一个整数 n

接下来 n 行,每行包含一个整数 mimi 个整数 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 表示所有序列的长度之和。

对于所有数据,n2,mi2,m2×105,0ai,j2×106

  • Subtask1(10pts):m100
  • Subtask2(20pts):m1000
  • Subtask3(30pts):m5×104
  • Subtask4(40pts):m2×105