Bubble Bucket Sort

Interview

Time limit1sMemory limit512 MB

Summary

Partition n bubble sizes into at most b buckets to minimize the sum of squared differences between the largest and smallest size in each bucket.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Greedy, Array
Solved: No attempts yet

Problem

Belinda loves blowing bubbles. After a long day of blowing bubbles, Belinda thinks it would be a good idea to sort the bubbles into buckets to store for the winter.

Each bubble must be placed in a bucket, and she would like the bubbles in each bucket to be as close to the same size as possible. The score of a bucket is the square of the difference in size of the largest and smallest bubble in that bucket. Belinda may put as many or as few bubbles into each bucket as she wishes. If a bucket is empty, its score is 0.

For example, if the buckets contained: [1, 2, 3], [3, 5], [4, 4], the total score would be (3 − 1)2 + (5 − 3)2 + (4 − 4)2 = 8. Given the sizes of the bubbles, what is the minimum total score that Belinda can achieve?

Input

The first line contains two integers n (1 ≤ n ≤ 200), which is the number of bubbles, and b (1 ≤ b ≤ 200), which is the number of buckets.

The next n lines describe the bubbles. Each of these lines contains a single integer k (1 ≤ k ≤ 109), which is the size of this bubble.

Output

Display the minimum total score that Belinda can achieve.

Examples2

Example 1
Input
```
5 3
1
2
3
4
5
```
Expected output
```
2
```
Example 2
Input
```
3 2
117
1337
101
```
Expected output
```
256
```