F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Division

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 999999/400000 K (Java/Others)
Total Submission(s): 8492    Accepted Submission(s): 3274

Problem Description
Little D is really interested in the theorem of sets recently. There¡¯s a problem that confused him a long time.
Let T be a set of integers. Let the MIN be the minimum integer in T and MAX be the maximum, then the cost of set T if defined as (MAX ¨C MIN)^2. Now given an integer set S, we want to find out M subsets S1, S2, ¡­, SM of S, such that

and the total cost of each subset is minimal.

Input
The input contains multiple test cases.
In the first line of the input there¡¯s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains two integers N (¡Ü 10,000) and M (¡Ü 5,000). N is the number of elements in S (may be duplicated). M is the number of subsets that we want to get. In the next line, there will be N integers giving set S.

Output
For each test case, output one line containing exactly one integer, the minimal total cost. Take a look at the sample output for format.

Sample Input
2
3 2
1 2 4
4 2
4 7 10 1


Sample Output
Case 1: 1
Case 2: 18


Hint
The answer will fit into a 32-bit signed integer.

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-06-17 03:15:58, Gzip enabled Administration