It is the autumn of 21XX.
Xiaocheng is a fourth-year undergraduate student in the Department of Naval Architecture at THU (Tomorrow Happy University). To graduate successfully, Xiaocheng has carefully read over a dozen highly cited conference papers from the past few years and plans to design a new type of spaceship under the guidance of authoritative theories.
This is a ring-shaped spaceship composed of $N$ cabins arranged in sequence. The design length of the $i$-th cabin is $L_i$. To provide energy for the spaceship, $K$ energy absorbers need to be installed on the surface of the spaceship.
According to authoritative theory, these absorbers should be distributed as evenly as possible across the surface of the spaceship. That is to say, Xiaocheng needs to divide the $N$ cabins of the spaceship into $K$ parts (each part consisting of a continuous segment of cabins) and configure one energy absorber for each part. Let $s_i$ be the total length of the $i$-th part; the goal is to minimize the variance:
$$\sum_{i=1}^{K} (s_i - s_{avg})^2$$
where $s_{avg}$ is the average length of the $K$ parts.
However, this problem is too difficult for a fourth-year undergraduate like Xiaocheng. Can you help him complete the design? For convenience, output the product of the minimum variance and $K^2$.
Input
The first line contains two integers $N$ and $K$.
The second line contains $N$ integers $L_1, L_2, \dots, L_N$, separated by spaces, representing the lengths of each cabin in order.
Output
Output a single integer representing the product of the minimum variance and $K^2$.
Constraints
There are 10 test cases in total. The data scale for each test case is as follows:
| Test Case | $N$ | $K$ | Test Case | $N$ | $K$ |
|---|---|---|---|---|---|
| #1 | $N = 1,000$ | $K = 2$ | #6 | $N = 50$ | $K = 6$ |
| #2 | $N = 100,000$ | #7 | $N = 100$ | $K = 7$ | |
| #3 | $N = 100$ | $K = 3$ | #8 | $N = 200$ | $K = 10$ |
| #4 | $N = 100,000$ | #9 | $N = 300$ | $K = 15$ | |
| #5 | $N = 300,000$ | #10 | $N = 400$ | $K = 20$ |
For 100% of the data, $1 \le L_i \le 1,000$.
Examples
Input 1
5 2 4 2 6 1 3
Output 1
0
Input 2
5 3 4 2 6 1 3
Output 2
24
Note
In the first example, the spaceship needs to be divided into 2 segments. The optimal division is $[2, 6]$ and $[1, 3, 4]$.
In the second example, the spaceship needs to be divided into 3 segments. The optimal division is $[4, 2]$, $[6]$, and $[1, 3]$.