题目背景

“为什么要离开我！”

“因为你没玩儿转！”

“我玩儿转了！”

“那好，你现在就给我维护这么一个式子！”

“为什么要出这么毒瘤的东西。”

“为了恶心你。”

“......”

$…………………………….$

题目描述

你的 $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$ 。

输出格式

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

3 2
1 2 3

32

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

1140

提示

• 对于 $30 \%$ 的数据，$m≤n≤500$；

• 另有 $20 \%$ 的数据，保证 $m=2$；

• 对于 $100 \%$ 的数据，$m≤n≤100000$，$1≤x_i≤1000$。