Busy Beaver is taking his first exam at the Maximally Intensive Testing Institute of Technology (MITIT). The exam is long and time is limited, so he needs to plan a strategy.

The exam is $M$ minutes long, with $N$ problems. The $i^\text{th}$ problem has a positive integer difficulty value, $d_i$. A problem with difficulty $d$ takes $d$ minutes to do, and is worth $d+1$ points. There is no partial credit for completing part of a problem.

Also, if Busy Beaver turns in the exam $X$ minutes before time is up ($0 \le X \le M$), he will receive $X$ bonus points added to his score.

What is the maximum possible score Busy Beaver could get?

Input

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $N$, $M$ ($1 \le N \le 10^5$, $1 \le M \le 10^9$).

The second line of each test case contains $N$ space-separated integers $d_1, \dots, d_N$ ($1 \le d_i \le 10^9$).

It is guaranteed that the sum of $N$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer: the maximum possible score.

Scoring

• ($15$ points) There is sufficient time to finish all of the problems.
• ($15$ points) All the problems have the same difficulty.
• ($70$ points) No additional constraints.

Examples

Input 1

4
4 7
1 2 3 4
4 45
15 10 5 10
5 10
20 30 40 50 60
5 10
8 4 13 5 7

Output 1

10
49
10
12

Note

In the first test case, Busy Beaver can do the problems with difficulties $1$, $2$, and $4$, in $7$ minutes. Busy Beaver will get $2 + 3 + 5 = 10$ points this way (no bonus points, because there is no extra time remaining).

In the second test case, Busy Beaver can do all four problems with 5 minutes to spare, and get a total of $49$ points: $16 + 11 + 6 + 11 = 44$ points from the problems, plus $5$ bonus points.

In the third test case, Busy Beaver cannot do any one of the problems within the given time! So the best thing to do is to submit a blank exam right after the timer starts, which gives $10$ bonus points.

In the fourth test case, Busy Beaver can do the two problems with difficulties $4$ and $5$, in $9$ minutes; Busy Beaver will receive $1$ bonus point since there is $1$ minute remaining, and get $5 + 6 + 1 = 12$ points in total.