F. Nafis and Mex
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially there is a value $$$y=0$$$, and an array $$$A$$$ of $$$N$$$ integers. You have to pick $$$K$$$ non-empty subsequences (not necessarily contiguous). Score of each subsequence is its $$$\rm{mex}$$$ (mex of a sequence is the minimum non-negative integer that doesn't exist in the sequence).

Pick any $$$K$$$ different non-empty subsequences and arrange their scores in any order, then add the scores with odd indices to $$$y$$$ and subtract the scores with even indices from $$$y$$$. More formally, let $$$S$$$ be the sequence of ordered scores, then $$$y=S_1-S_2+S_3-\dots-(-1)^K S_K$$$.

Find the minimum possible value of $$$y$$$.

Two subsequences are different if there is at least one index that doesn't exist in exactly one of the subsequences. (So there are $$$2^N-1$$$ non-empty subsequences.)

Input

The first line of input contains an integer $$$T$$$ ($$$1 \le T \le 100000$$$) — number of test cases

Each test case contains 2 lines:

First line contains two integers $$$N$$$ ($$$1 \le N \le 100000$$$) and $$$K$$$($$$1 \le K \le \min(10^9,2^N - 1)$$$) — size of the array and number of subsequences you have to pick.

Second line contains $$$N$$$ integers of the array $$$A$$$. For each $$$i$$$, $$$0 \le A_i \le 10^9$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$100000$$$.

Output

For every test case, you have to output a single integer — the minimum possible value of $$$y$$$ you can obtain.

Example
Input
3
6 4
0 0 2 3 1 4
8 7
1 2 3 0 1 2 4 6
3 1
1 5 2
Output
-10
-15
0