忘情

题目背景

“为什么要离开我!” “因为你没玩儿转!” “我玩儿转了!” “那好,你现在就给我维护这么一个式子!” “为什么要出这么毒瘤的东西。” “为了恶心你。” “......” $…………………………….$

题目描述

你的 $npy$ 为了恶心你,特地请了四位大神和一个辣鸡! $\rm hdxrie$ 说:“我们得求和。”于是有了 $\sum\limits_{i=1}^{n}x_i $ 。 $\rm Imagine$ 说:“我们得有平均数。”于是有了 $\bar x $ 。 $\rm TimeTraveller$ 说:“我们得有加减乘除。”于是有了一些恶心的组合。 $\rm Althen·Way·Satan$ 说:“我们还得有平方。”于是我们将它平方。 最垃圾的 $\rm ZredXNy$ 说:“那我帮你们整合一下。” 于是,我们得到了这么一个式子 $:$ $$\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}$$ 我们定义一段序列的值为这个,其中 $n$为此序列的元素个数。 我们给定一段长度为 $n$ 的序列,现在要求将它分成 $m$ 段,要求每一段的值的总和最小,求出这个最小值。

输入输出格式

输入格式


第一行两个正整数,分别为 $n$,$m$,定义见题面。 接下来一行为 $n$ 个正整数,依次给出这个序列的每个元素的值 $x_i$ 。

输出格式


一个整数,求出这个最小值。

输入输出样例

输入样例 #1

3 2
1 2 3

输出样例 #1

32

输入样例 #2

10 3
1 2 3 4 5 6 7 8 9 10

输出样例 #2

1140

说明

- 对于 $30 \%$ 的数据,$m≤n≤500$; - 另有 $20 \%$ 的数据,保证 $m=2$; - 对于 $100 \%$ 的数据,$m≤n≤100000$,$1≤x_i≤1000$。