Czech Technical University in Prague
Faculty of Mathematics and Physics, Charles University in Prague
Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava
Faculty of Informatics and Information Technologies, Slovak University of Technology
Faculty of Informatics, Masaryk University
Faculty of Management Science and Informatics, University of Zilina
CTU Open Contest 2009
Suspicious Stocks
ss.c, ss.C,, ss.p
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.
Input Specification
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.
Output Specification
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 1000
1200 40 10
3 10
5 10
Output for Sample Input