"Weddings are basically funerals with cake Morty"

Birdperson has invited Rick and Morty to attend his marriage party. Rick doesn't like to go to marriage parties but Morty wants to go, as Birdperson is a very close friend. Also, Birdperson is king of Bird-planet and wants to compensate for the travel expenses for Rick's family. Bird-planet is many light years away from the earth but that is not the problem as Rick has Space Cruiser with hyperspeed.

Space cruiser needs 1 unit of fuel to travel 1 light year but it has a limited capacity 'C' so they may need to refuel in-between. There are many planets between Birdplanet and Earth and the fuel pricing is different on each planet.

Let Earth is numbered as '1' and bird-planet as 'N+1' then they can fuel at n planets (including earth). Distance between any two consecutive planets is 'D' light-years.

Evil Rick wants to maximize the expense of fueling and Birdperson knows this so he put a condition that on arrival there should be zero fuel in the tank.

Your task is to maximize the expense and it is obvious that they can't fuel at bird-planet. Initially, there is zero fuel in the tank.

Input

The first line contains T, the number of test cases. Then the test cases follow.

The first line of each test case contains N, C and D, Number of planets for fueling (including Earth), Capacity of the fuel tank and distance between two consecutive planets

Second-line contains A1 A2 A3… AN, where Ai denotes the price of 1 unit of fuel on ith planet.

Output

For each test case print the maximum possible expense.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 10⁵

1 ≤ D ≤ 10⁵

D ≤ C ≤ 10⁵

1 ≤ Ai ≤ 10⁹

Example

Input:
1
3 5 3
1 5 2
Output:
30

Explanation

• As N=3 so Birdplanet will be 4th planet and hence they will need to travel 3*3=9 light year.
• First they will buy 3 unit fuel from 1st planet to go to 2nd planet, expense: 3*1=3
• They will buy 5 unit of fuel (up to full capacity) at 2nd planet, expense: 5*5=25
• There will be 2 unit of fuel remaining on reaching 3rd planet so the need to buy only 1 more unit of fuel to reach Birdplanet, expense: 1*2=2
• Total expense 3+25+2=30