array-divider

You have recently found an array of N non-negative integers. You like it a lot but unfortunately it is too long. So now you are going to divide in exactly K blocks and each of the blocks should  consist of several consecutive elements of the array.

There are many ways to divide the array. You wish to minimize the value X calculated in the following way :
Let's suppose that sums of the elements in blocks are S1, S2 ... Sk correspondingly. X = sum (Si - Sj)^2  through all i, j from 1 to K and i ≤ j.

Before dividing the array you are interested in the exact value of X. So the only thing you have to do is to find it.

Input
The first line contains two space-separated integers N and K.
The second line contains N space-separated integers - your array.

Output
Output one integer - answer for the question.

Constraints
N ≤ 500, K ≤ 300, K ≤ N
Each element of the array is an integer from  0 to 10^5
N ≤ 20 in 40% of the test data.

SAMPLE INPUT
7 3
1 7 3 5 1 4 4
 

SAMPLE OUTPUT
2

Explanation

The best way is to divide the array in such 3 groups : (1, 7), (3, 5), (1, 4, 4) with Si correspondingly 8, 8, 9

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming


Solutions: