B. Ahmad and Pairs Syndrome
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

1, 2, 3, ..., 9000 and 9001! It's over 9000! — Ahmad said while counting the number of problems he wrote about pairs.

You're given an array $$$a$$$ of $$$n$$$ integers; let's imagine a multiset $$$S$$$ containing all the absolute differences between any two elements $$$a_i$$$ and $$$a_j$$$ for all $$$1 \leq i, j \leq n$$$ and $$$i \neq j$$$.

Here, the absolute difference between two integers $$$x$$$ and $$$y$$$ is $$$|x - y|$$$.

What's the sum of the largest $$$m$$$ elements in the multiset $$$S$$$?

Input

The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq n \cdot (n - 1))$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^7)$$$.

Output

For each test case, print one integer, the sum of the $$$m$$$ largest elements in the set $$$S$$$.

Example
Input
3
3 2
1 2 3
5 5
5 4 3 2 1
7 5
3 2 1 4 5 7 6
Output
4
17
27