题目描述
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
输入格式
见题面
输出格式
见题面