Optimal Stock Trading Strategy

Bessie and the cows, after enduring losses in the home mortgage market, are now venturing into stocks. They have knowledge of the current prices and the future prices for D days (where D satisfies \(2\le D\le10\)), and they have S different stocks (\(2\le S\le50\)). They also start with an initial amount of money \(M\) (\(1\le M\le200000\)).

For each stock, you are given a list of prices over the D days. The price \(PR_{sd}\) of stock s on day d is an integer satisfying \(1\le PR_{sd}\le1000\). On any day (except the final day), you may decide to purchase an integer number of shares of any stock using some or all of your money, and on a later day you may sell these shares. You do not have to invest all your money and you are allowed to hold money in reserve.

Your goal is to develop a strategy of buying and selling stocks such that after selling on the final day (day \(D\)), your total money is maximized. It is guaranteed that profitable strategies will not yield a profit of more than 500,000 units of money.

Example:

In this case, with \(S=2\), \(D=3\), and \(M=10\), the optimal strategy is as follows:

• On day 1, purchase 1 share of stock A at a price of 10.
• On day 2, sell stock A at 15. Now you have 15 units of money.
• Immediately on day 2, use the money to buy 1 share of stock B at 11 (you spend 11 and keep 4 units in reserve).
• On day 3, sell stock B at 20, ending with a total of \(4+20=24\) units of money.

Your task is to compute the maximum amount of money achievable on day \(D\) by following an optimal sequence of transactions.

inputFormat

The first line contains three space-separated integers: \(S\), \(D\), and \(M\).

The next \(S\) lines each contain \(D\) space-separated integers, where the \(i\)-th line represents the prices of the \(i\)-th stock over the \(D\) days.

outputFormat

Output a single integer: the maximum amount of money obtainable on the final day (day \(D\)) after executing an optimal series of buy-and-sell transactions.

sample

2 3 10
10 15 15
13 11 20

24