Description

This will be a ring-shaped spaceship, consisting of $N$ cabins in order. The designed length of the $i$-th cabin is $L_i$.

To provide energy for the spaceship, $K$ space energy absorbers need to be installed on the spaceship. According to authoritative theories, these absorbers should be distributed as evenly as possible over the surface of the spaceship. That is, Xiao Cheng needs to divide all $N$ cabins of the spaceship into $K$ parts (each part includes a consecutive segment of cabins), and assign one energy absorber to each part. Let the sum of cabin lengths in the $i$-th part be $s_i$; then the variance should be minimized as much as possible.

However, this problem is too difficult for Xiao Cheng, who is already a senior undergraduate student. Can you help him finish the design? For convenience, output the product of the minimum variance and $K^2$.

Input Format

The input consists of two lines.

The first line contains two integers $N, K$.

The second line contains $N$ integers $L_1, L_2, \ldots, L_N$ separated by spaces, representing the length of each cabin in order.

Output Format

Output one line with one integer, representing the product of the minimum variance and $K^2$.

5 3
4 2 6 1 3

24

Hint

Constraints

For $100\%$ of the testdata, $N \le 400$, $K \le 20$, and $1 \le L_i \le 10^3$.

Translated by ChatGPT 5