Background

"Why are you leaving me!"

"Because you can't handle it!"

"I can handle it!"

"Fine, then maintain such a formula for me right now!"

"Why would you give such a nasty thing."

"To annoy you."

"......"

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

Problem Description

Your $npy$, in order to annoy you, specially invited four gurus and one noob!

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

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

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

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

The worst $\rm ZredXNy$ said: "Then I'll help you merge them."

So we get the following expression:

$$\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 expression, where $n$ is the number of elements in the sequence.

Given a sequence of length $n$, you now need to split it into $m$ segments. The sum of the values of all segments should be as small as possible. Output this minimum value.

Input Format

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

The next line contains $n$ positive integers, giving the value of each element $x_i$ in order.

Output Format

Output one integer, the minimum value.

3 2
1 2 3

32

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

1140

Hint

• For $30\%$ of the data, $m \le n \le 500$.
• For another $20\%$ of the data, it is guaranteed that $m = 2$.
• For $100\%$ of the data, $m \le n \le 100000$, $1 \le x_i \le 1000$.

Translated by ChatGPT 5