#1173. 「AHOI / HNOI 2017」礼物

    ID: 1173 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>其他数学DFT(含 NTT)及FFT2017HNOIAHOI

「AHOI / HNOI 2017」礼物

题目描述

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 nn 个装饰物,并且每个装饰物都有一定的亮度。

但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的整数 cc(可能是负数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 1,2,,n1, 2,\cdots, n,其中 nn 为每个手环的装饰物个数,第一个手环的 ii 号位置装饰物亮度为 xix_i,第二个手环的 ii 号位置装饰物亮度为 yiy_i,两个手环之间的差异值为(参见输入输出样例和样例解释):

i=1n(xiyi)2\sum_{i = 1}^n (x_i - y_i)^2

麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?

输入格式

输入数据的第一行有两个数 n,mn, m,代表每条手环的装饰物的数量为 nn,每个装饰物的初始亮度小于等于 mm
接下来两行,每行各有 nn 个数,分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

输出格式

输出一个数,表示两个手环能产生的最小差异值。注意在将手环改造之后,装饰物的亮度可以大于 mm

样例

5 6
1 2 3 4 5
6 3 3 4 5
1

需要将第一个手环的亮度增加 11,第一个手环的亮度变为:2,3,4,5,62, 3, 4, 5, 6。旋转一下第二个手环,对于该样例,是将第二个手环的亮度 6,3,3,4,56, 3, 3, 4, 5 向左循环移动一个位置,使得第二手环的最终的亮度为:3,3,4,5,63, 3, 4, 5, 6

此时两个手环的亮度差异值为 11

数据范围与提示

对于 30%30\% 的数据,n500,m10n\le 500, m\le 10
对于 70%70\% 的数据,n5000n\le 5000
对于 100%100\% 的数据,1n50000,1m100,1aim1\le n\le 50000, 1\le m\le 100, 1\le a_i\le m