Pine has begun a journey from location S to location T. The road from S to T can be divided into $n$ segments, with rest stops located at the boundaries between adjacent segments. Pine plans to reach T in $m$ days. Except for the $m$-th day, Pine must spend every night at a rest stop. Therefore, each segment of the road must be completed within a single day. Pine wants the distance traveled each day to be as similar as possible, so he hopes to minimize the variance of the distances traveled each day. Help Pine find the minimum possible variance. Let the variance be $v$. It can be proven that $v \cdot m^2$ is an integer. To avoid precision errors, output the value of $v \cdot m^2$.

Input

The first line contains two integers $n$ and $m$. The second line contains $n$ integers, representing the lengths of the $n$ road segments.

Output

A single integer, the value of the minimum variance multiplied by $m^2$.

Examples

Input 1

5 2
1 2 5 8 6

Output 1

36

Constraints

For 30% of the data, $1 \le n \le 10$. For 60% of the data, $1 \le n \le 100$. For 100% of the data, $1 \le n \le 3000$. It is guaranteed that the total distance from S to T does not exceed $30000$.