Subarray Squares

Given an array of n elements, your task is to divide into k subarrays. The cost of each subarray is the square of the sum of the values in the subarray. What is the minimum total cost if you act optimally?

Input

The first input line has two integers n and k: the array elements and the number of subarrays. The array elements are numbered 1,2,\dots,n. The second line has n integers x_1,x_2,\dots,x_n: the contents of the array.

Output

Print one integer: the minimum total cost.

Constraints

$1 \le k \le n \le 3000$

$1 \le x_i \le 10^5$

Example

Input

8 3
2 3 1 2 2 3 4 1

Output

110

Explanation: An optimal solution is [2,3,1], [2,2,3], [4,1], whose cost is (2+3+1)^2+(2+2+3)^2+(4+1)^2=110.