![]() |
||||||||||
|
||||||||||
DivisionTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 999999/400000 K (Java/Others)Total Submission(s): 8676 Accepted Submission(s): 3327 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 – 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
Sample Output
Hint The answer will fit into a 32-bit signed integer. Source | ||||||||||
|