Preparing NOJ

Suspicious Stocks

1000ms 65536K


The corruption is always extremely difficult to prove. Even if we know that some people accept bribes, it is almost impossible to punish them, because the only witnesses are them and the people who offered the bribe. Neither of them is likely to testify.
One way to prove that something illegal has happened is to count the money a person has and then give evidence that it was impossible for him/her to earn that money legally. However, this is not so easy. For example, the person may easily claim that the money have been donated by their uncle or earned by trading stocks.
ACM would like to be able to verify these explanations. Since it is impossible to verify the existence of “uncles”, we will concentrate on the stocks. You are given the history of stock prices, and your task is to compute the maximal profit that could possibly be earned by buying and selling the stock.


The input will consist of several test scenarios, each of them consisting of two lines of text. The first line of a scenario contains two positive integers D and M (1 D 70000, 1 M 40000) separated by a space. D is the number of days when the trading took place, M is the amount of money available at the beginning.
The second line of each scenario contains D positive integers p1, p2, p3, . . . , pD (1 pi 40000) separated by a space. The number pi denotes the price of one piece of stock at day i, meaning it is possible to buy or sell one piece for that price on that day.
The last scenario is followed by a line containing single zero.


For each scenario, output one line containing one number: The maximum profit that could be achieved by at most one Buy operation followed by one Sell operation. Assume that there is no stock at the beginning and that it is possible to do only one Buy during the whole trading.
For simplicity, assume that it is possible to buy as many pieces of stock as there are money for, but we can only buy and sell whole pieces (integer number) of stock, not fractions. For example, if the stock price is $3 and we have $11, we can only buy 3 pieces.
The Buy operation is followed by exactly one Sell operation on some of the following days. Of course, it is possible (and recommended) to sell all the pieces of stock to maximize profit.

Sample Input:

3 1
1 2 3
3 1 0 0 0
1 2 0 0 4 0 1 0
3 1 0
3 4 5
5 1 0
2 3 7 1 4

Sample Output:




本题由旧版NOJ导入,来源:CTU Open 2009



Provider NOJ

Code NOJ1567


Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10


Nothing Yet