Stock

Recently, the Chinese stock market begins to heat up slowly. It is said that in 2009 China's Stock market will re-enter the bull market. Let’s pay some attention to the stock.

Stock is defined as a purely economic issue, it is actually representative of your company's ownership of the shares. But in fact most investors regard it as a kind of commodities, not the production which are made in the factories. Since it is a commodity, there is measurement problem. Fruits are bought by jin, TV sets are bought by set. While the stock is bought in share. Stock and TV set here in set is similar. That is, we can not buy half-shares, and at least buy one share. Of course, stock and fruit, TV set, are different. Stock is so different as the price is changing at all time. Everyone can buy it legally in the trading market. Stock trading costs transaction fees. And the calculation is quite complicated so we don’t dive into this.

To make it easier, we have the problem simplified. First of all, ignore the price changing within a day, meaning that only one constant price on a certain day. Then assuming that only to pay fees when stock are sold, the transaction fee is a fixed value of s.

For example, if the transaction fee is $100. The stock price on the first day is $10 per share. We have $10,000, so we can buy 1,000 shares. The next day, the stock price rise to $11 per share. We sell all the 1,000 shares, so get $11,000. It cost $100 for the fee. So the profit is $900.

In this problem the transaction times is unlimited. You can sell and buy stock time and time again if you like. Now, if we know the stock prices in n trading days, the fee and the initial funding. So, how much money can we earn at most in the n days?

There are multiple cases.

The first line contains the number of test cases t.

For each case, the first line contains three integers n (1<n<=3000), s (0<=s<=10000), p (0<p<=100000), respectively, the number of trading days, fee and initial funding. The second line contains n positive real numbers which are greater than 0 (up to two significant figures after the decimal point), the prices are given in chronological order of the n trading days.

For each case, output a number, that is this the maximum amount of money you can earn, retained two decimal places. The results are not larger than 10^9.

3
4 10 100
10.00 1.00 12.00 10.00
3 10 100
10.5 5.3 1.9
5 10 100
4 1 8 2 5 

1090.00
0.00
1865.00 

2009 Multi-University Training Contest 15 - Host by BUAA