{"raw_statement":[{"iden":"statement","content":"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.\n\nGiven 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.\n\nThe 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.\n\nEach 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).\n\nFor each dataset, write out on one line the maximum profit you could make.\n\nYou 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\n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"For each dataset, write out on one line the maximum profit you could make."},{"iden":"examples","content":"Input112 100000099 100 101 102 100 99 97 101 102 105 104 104Output82472"},{"iden":"note","content":"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"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of datasets.  \nFor each dataset $ k \\in \\{1, \\dots, t\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the number of days ($ 1 \\leq N_k \\leq 100 $).  \n- Let $ W_k \\in \\mathbb{R}^+ $ denote the initial capital ($ 0 < W_k \\leq 1{,}000{,}000 $).  \n- Let $ P_k = (p_{k,1}, p_{k,2}, \\dots, p_{k,N_k}) $ be a sequence of forecasted stock prices, where $ p_{k,i} \\in \\mathbb{R}^+ $ and $ 0 < p_{k,i} \\leq 1000 $.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 10 $  \n2. For each $ k \\in \\{1, \\dots, t\\} $:  \n   - $ 1 \\leq N_k \\leq 100 $  \n   - $ 0 < W_k \\leq 1{,}000{,}000 $  \n   - $ 0 < p_{k,i} \\leq 1000 $ for all $ i \\in \\{1, \\dots, N_k\\} $  \n3. Only one buy-sell pair is allowed: buy on day $ i $, sell on day $ j $, with $ 1 \\leq i < j \\leq N_k $.  \n4. Number of stocks bought/sold must be an integer.  \n\n**Objective**  \nFor each dataset $ k $, compute the maximum profit:  \n$$\n\\max_{\\substack{1 \\leq i < j \\leq N_k \\\\ p_{k,i} < p_{k,j}}} \\left( \\left\\lfloor \\frac{W_k}{p_{k,i}} \\right\\rfloor \\cdot (p_{k,j} - p_{k,i}) \\right)\n$$  \nIf no profitable transaction exists, the profit is 0.","simple_statement":"You have W money and N days of stock prices. Buy on one day, sell on a later day, maximize profit. Buy as many whole shares as possible. Print max profit.","has_page_source":false}