P17331 "TPOI-2A" Min Mex

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$.

**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$.

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

**[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**. |$\text{Subtask}$|Score|Special property|Dependencies| |:-:|:-:|:-:|:-:| |$1$|$30$|All $a_i$ are pairwise distinct|None| |$2$|$30$|$n \le 8$|^| |$3$|$40$|None|$1,2$| 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