Problem description.
One day Toretto wanted to make some extra money. We all know his obsession with cars so all he could manage to get hold of, was some information regarding the buying and selling prices of cars for the next N days.
The buying and selling prices for one car on day i are same and equal to Pi where (1<=i<=N). Toretto initial has M dollars with him. He can buy a certain number of cars and then sell it no more than once in N days.
Note: There can be atmost one such transaction of buying and selling in these N days.
What is the maximum amount of money Toretto can have by the end of day N?

Input
The first line contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two spaces integers N and M denoting the total number of days and the initial money with Toretto.
The next line of each test case contains N spaces integers Pi denoting the price of a car on day i.

Output

For each test case output a single line containing the answer to the problem.

Constraints
1<=T<=20
1<=N, M<=2000
1<=Pi<=2000

Example
Input:
3
2 5
4 8
4 100
10 7 6 4
4 100
10 6 7 4

Output:
9
100
116

见题面

见题面