Problem Description

For an array $a$, define $\operatorname{mex}\{a\}$ as the smallest positive integer that does not appear in $a$.

Esc gives you an array $a$ of length $n$. You may perform the following operation any number of times:

• Choose an integer $i$ with $1 \le i \le n$ and an integer $x$ with $0 \le x < a_i$. Pay a cost of $x$ to change $a_i$ into $a_i - x$.

Find the minimum total cost to make $\operatorname{mex}\{a\}=k$. If it is impossible to make $\operatorname{mex}\{a\}=k$ no matter how many operations you perform, output $-1$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, meaning the number of test cases.

For each test case:

The first line contains two integers $n,k$.

The second line contains $n$ integers $a_i$.

Output Format

For each test case, output one integer per line representing the answer.

5
4 3
2 3 4 5
3 1
3 2 1
3 2
3 2 1
4 3
1 1 2 4
5 3
1 1 1 1 1

2
-1
1
0
-1

Hint

[Sample #1 Explanation]

For the first test case, you can change the original array to 2 1 4 5, with a cost of $2$.

For the second test case, it is clear that there is no valid solution.

[Constraints]

This problem uses bundled testdata and enables subtask dependencies.

For $100\%$ of the testdata, it is guaranteed that $1\le T\le 10^3$, $1\le k,n\le2\times10^5$, $\sum n \le 10^6$, and $1\le a_i\le10^9$.

Translated by ChatGPT 5