Consider the problem faced by a stockbroker trying to sell a large number of shares of stock in a company whose stock price has been steadily falling in value. It is always hard to predict the right moment to sell stock, but owning a lot of shares in a single company adds an extra complication: the mere act of selling many shares in a single day will have an adverse eect on the price.

Since future market prices, and the eect of large sales on these prices, are very hard to predict, brokerage rms use models of the market to help them make such decisions. In this problem, we will consider the following simple model. Suppose we need to sell x shares of stock in a company, and suppose that we have an accurate model of the market: it predicts that the stock price will take the values p1,p2,...,pn over the next n days. Moreover, there is a function f(y) that predicts the eect of large sales: if we sell y shares on a single day, it will permanently decrease the price by f(y) from that day onward. So, if we sell y1 shares on day 1, we obtain a price per share of p1 f(y1), for a total income of y1 (p1 f(y1)). Having sold y1 shares on day 1, we can then sell y2 shares on day 2 for a price per share of p2 f(y1)f(y2) this yields an additional income of y2 (p2 f(y1)f(y2)). This process continues over all n days. (Note, as in our calculation for day 2, that the decreases from earlier days are absorbed into the prices for all later days.)

Design an ecient dynamic programming algorithm that takes the prices p1,...,pn) and the function f(x) (written as a list of values f(1),f(2),...,f(x)) and determines the best way to sell x shares by day n. In other words, nd natural numbers y1,y2,...,yn so that x = y1 + ... + yn, and selling yi shares on day i for i = 1,2,...,n maximizes the total income achievable. You should assume that the share value pi is monotone decreasing, and f(x) is monotone increasing; that is, selling a larger number of shares causes a larger drop in the price. Your algorithms running time can have a polynomial dependence on n (the number of days), x (the number of shares), and p1 (the peak price of the stock).

Example: Consider the case when n = 3; the prices for the three days are 90, 80, 40; and f(y) = 1 for y 40,000 and f(y) = 20 for y > 40,000. Assume you start with x = 100,000 shares. Selling all of them on day 1 would yield a price of 70 per share, for a total income of 7,000,000. On the other hand, selling 40,000 shares on day 1 yields a price of 89 per share, and selling the remaining 60,000 shares on day 2 results in a price of 59 per share, for a total income of 7,100,000.