TTBRM  To the Birdplanet
"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 Birdplanet and wants to compensate for the travel expenses for Rick's family. Birdplanet 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 inbetween. There are many planets between Birdplanet and Earth and the fuel pricing is different on each planet.
Let Earth is numbered as '1' and birdplanet as 'N+1' then they can fuel at n planets (including earth). Distance between any two consecutive planets is 'D' lightyears.
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 birdplanet. 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
Secondline 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^{5}
1≤D≤10^{5}
D≤C≤10^{5}
1≤Ai≤10^{9}
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
hide comments
kunal9724kg:
20200111 11:23:26
Last edit: 20200113 21:56:30 

sonuverma:
20191207 12:48:20
Thanks for the compliment :D :) 

:D:
20191201 00:27:55
Very nice problem. Description is also fun. This must be the only problem where maximizing cost makes sense :) 
Added by:  17 Sonu Verma 
Date:  20191125 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 