401842: GYM100541 A Stock Market

An expert in deep learning has developed a new method for stock market forecasting. According to his method, the forecasted stock prices of VAIP for the next N days are p₁, p₂, p₃, …, p_N, where p_i denotes the forecasted stock price for the i_th day.

Given p_i and the total amount of money W, find a way to buy and sell VAIP stocks to maximize the profit. You can only buy VAIP stocks in one day, or you don’t buy at all. The number of stocks bought or sold must be an integer.

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 10. The following lines describe the datasets.

Each dataset consists of two lines where the first line contains two space-separated integers N (N ≤ 100) and W (0 < W ≤ 1, 000, 000) where W is the amount of money you will invest in the stock. The second line contains N space-separated integers representing p_i (0 < p_i ≤ 1000).

For each dataset, write out on one line the maximum profit you could make.

1
12 1000000
99 100 101 102 100 99 97 101 102 105 104 104

82472

You should buy 10309 (=1000000 div 97) stocks at the price of 97 and sell 10309 stocks at the price of 105 to get the maximum profit of (105-97)*10309