16 人解决，24 人已尝试。
17 份提交通过，共有 58 份提交。
5.4 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
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 \leq D \leq 70000, 1 \leq M \leq 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 $p_1, p_2, p_3, \ldots, p_D$ $(1 \leq pi \leq 40000)$ separated by a space. The number $p_i$ 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 dollars and we have 11 dollars, 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.
3 1 1 2 3 3 1000 1200 40 10 3 10 3 4 5 5 10 2 3 7 1 4 0
2 0 6 30
16 人解决，24 人已尝试。
17 份提交通过，共有 58 份提交。
5.4 EMB 奖励。