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
Author ID 
Password 
 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
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