Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID


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.

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.


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

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


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