D. Coins 3
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedro has $$$n$$$ coins, each with a value $$$m_i$$$. Pedro wants to pay exactly $$$k$$$ euros to the shopkeeper; to do this, he follows the following algorithm:

  • Sort the coins from highest to lowest value.
  • He takes out the coins in the specified order.
  • Each time he takes out a coin, he does the following: if the value is less than or equal to what he still needs to pay, he gives the coin to the shopkeeper; if it is greater, he keeps it in his pocket.

This algorithm does not always work, and sometimes Pedro cannot manage to pay $$$k$$$ euros. He believes it is because he is missing coins, which is why he asks you for money.

Knowing what coins Pedro has, the amount he wants to pay, and the algorithm he uses to pay, what is the minimum amount of euros you need to give him so that he can pay? You can give it to him in more than one coin.

Input

The input starts with an integer $$$t$$$ indicating the number of cases.

Each case consists of two integers $$$n$$$ and $$$k$$$, followed by a line with $$$n$$$ integers $$$m_i$$$.

Output

For each case, write a line with the answer.

Scoring

$$$1 \leq t \leq 100$$$

33 Points: $$$1 \leq n,k,m_i \leq 100$$$

33 Points: $$$1 \leq n \leq 10^3$$$, $$$1 \leq m_i \leq 10^4$$$, $$$1 \leq k \leq 10^7$$$

34 Points: $$$1 \leq n \leq 10^4$$$, $$$1 \leq m_i \leq 10^9$$$, $$$1 \leq k \leq 10^{13}$$$

Example
Input
5
6 74
49 3 13 61 13 4
10 22
62 9 10 30 50 56 7 11 1 42
3 32
38 53 68
5 18
45 14 69 57 5
3 82
41 51 33
Output
0
0
32
4
31