题目描述

小诚准备设计一艘环形的太空飞船，由$N$个舱室顺序组成。第$i$个舱室的设计长度为$L_i$。为了给飞船提供能量，要在飞船上装置$K$个太空能量吸收器。 这些吸收器应该尽量均匀地分散在飞船表面。也就是说，小诚要把飞船所有$N$个舱室划分成 $K$个部分（每个部分包括连续一段舱室），并给每个部分配置一个能量吸收器。设第$i$个部分舱室的长度之和为$s_i$，则要令方差$\sum_{i=1}^{k}(s_i-s_{avg})^2$ 尽量小。其中$s_{avg}$ 是$K$个部分的平均长度。 可是，这个问题对于小诚来说太难了。你能否帮助他完成设计呢？ 为方便起见，输出方差最小值与K的平方的乘积。

输入

第一行，两个整数 $N，K$。 第二行，$N$个整数$L_1, L_2, …, L_N$，由空格隔开。依次表示每个舱室的长度。

输出

输出一行，为一个整数，表示方差最小值与$K^2$的乘积。

输入样例

5 2
4 2 6 1 3

输出样例

0

提示

【输入样例2】

5 3
4 2 6 1 3

【输出样例2】

24

【样例解释】 第一组样例。要将飞船分为$2$段，最优划分方法为$[2 6] [1 3 4]$。 第二组样例。要将飞船分为$3$段，最优划分方法为$[4 2] [6] [1 3]$。 【数据规模】 本题一共有10 个测试点。 下表是每个测试点的数据规模：

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。