401842: GYM100541 A Stock Market

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Stock Markettime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 p1, p2, p3, …, pN, where pi denotes the forecasted stock price for the ith day.

Given pi 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.

Input

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 pi (0 < pi ≤ 1000).

Output

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

ExamplesInput
1
12 1000000
99 100 101 102 100 99 97 101 102 105 104 104
Output
82472
Note

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

加入题单

上一题 下一题 算法标签: