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 effect on the price. Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms 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(·) that predicts the effect 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.)

Required:
Design an efficient algorithm that takes the prices p1,..., pn and the function f(·) (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, find 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.