To celebrate Children's Day, a mother of k kids comes to the shop to buy sweets. There are n boxes of sweets in the shop, the i-th box has wi sweets. The mother will choose which boxes to buy, and will divide all the bought boxes among the k kids. Each kid will receive several (maybe zero) boxes, and will count the total number of sweets he receives. Assume the i-th kid receives ci sweets, the unfairness is defined as ∑i=1kci2. To make all the kids happy, the mother will always divide boxes to minimize the unfairness. Note that she can not open any box to adjust the number of sweets inside it.
The mother is wondering which boxes to buy. She can not make her final decision. Please write a program to help the mother try all possible 2^n-1 non-empty subsets of boxes to buy, and figure out the minimum unfairness for each subset. Note that you only need to report the sum of the minimum unfairness among all 2^n-1 non-empty subsets.
The first line contains a single integer T(1≤T≤50), the number of test cases. For each test case:
The first line contains two integers nand m(1≤m≤n≤20, n+m≤23), denoting the number of boxes and the parameter mm.
The second line contains n integers w1,w2,…,wn (1≤wi≤50,000), denoting the number of sweets in each box.
It is guaranteed that there are at most 2 cases such that n>12.
1
5 4
1 2 3 4 52240
1180
930
884