It is said that writing wishing cards on New Year's Eve can bring good luck. You have written wishing cards and plan to give them to Little A.

You have invited $$$n$$$ friends to help you deliver the wishing cards. You plan to give the $$$i$$$-th friend $$$b_i$$$ wishing cards. The friends will visit Little A's house in the order of $$$1$$$ to $$$n$$$, and each will hand over all his $$$b_i$$$ wishing cards to Little A. Little A always remembers the friend who gives her the most wishing cards, so after the $$$j$$$-th friend's visit, she gains happiness equal to the largest number of cards received so far, that is, $$$\max(b_1, b_2, \ldots, b_j)$$$.

The $$$i$$$-th friend can carry at most $$$a_i$$$ cards, and the total number of cards cannot exceed $$$k$$$. Your task is to optimally choose values of $$$b_i$$$ so that the total happiness of Little A after $$$n$$$ visits is maximized under these constraints.

Note that some friends may carry no cards at all, Little A won't get mad.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 360$$$), the number of friends, and the maximum total number of cards.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le k$$$), the maximum number of cards each friend can carry.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$1800$$$.

Output

For each test case, output the maximum happiness Little A can get.

Note

In the first test case, the only way to distribute wishing cards is $$$b = [0,0,1]$$$.

In the third test case, $$$b = [1,0,4]$$$ is invalid because you only have $$$k = 4$$$ wishing cards.

In the fourth test case, one of the optimal ways to distribute wishing cards is to set $$$b = [2,0,5,0,0]$$$, in which Little A will gain $$$2+2+5+5+5=19$$$ happiness.

Wishing Cards

Examples