Problem Background

"Why did you leave me!"

"Because you didn't get it right!"

"I got it right!"

"Alright, then maintain this formula for me right now!"

"Why come up with such a toxic thing."

"To disgust you."

"......"

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

Problem Description

Your significant other is trying to disgust you, so they invited four great masters and a trashy one!

$\rm$ said: "We need to sum up." So we have $\sum\limits_{i=1}^{n}x_i$.

$\rm$ said: "We need an average." So we have $\bar x$.

$\rm$ said: "We need addition, subtraction, multiplication, and division." So we have some nasty combinations.

$\rm Althen·Way·Satan$ said: "We also need squares." So we square it.

The most trashy $\rm$ said: "Let me integrate them for you."

Thus, we got this formula:

$$\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}$$

We define the value of a sequence as this, where $n$ is the number of elements in the sequence.

Given a sequence of length $n$, we need to divide it into $m$ segments, and we want the sum of the values of each segment to be minimized. Find this minimum value.

Input Format

The first line contains two positive integers, $n$ and $m$, as defined in the problem statement.

The next line contains $n$ positive integers, representing the values of each element in the sequence, $x_i$.

Output Format

A single integer, representing the minimum value.

Sample Input and Output

Sample Input #1

3 2
1 2 3

Sample Output #1

32

Sample Input #2

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

Sample Output #2

1140

Notes/Hints

• For $30\%$ of the data, $m \leq n \leq 500$;
• For another $20\%$ of the data, $m = 2$;
• For $100\%$ of the data, $m \leq n \leq 100000$, $1 \leq x_i \leq 1000$.

见题面 Input 部分

见题面 Output 部分