Stock King Dongho

Time limit2sMemory limit128 MB

Summary

Given prices for C stocks over D days and starting cash M, find the maximum cash obtainable by buying and selling whole shares each day using knapsack-style dynamic programming.

Level: Medium7 of 10
Topics: Dynamic programming, Array, Math, Brute force
Solved: No attempts yet

Problem

Dongho wants to earn as much money as possible by trading stocks. He knows the prices of C stocks for each of the next D days.

He starts with M units of cash. On each day, he may buy and sell any whole number of shares at that day's listed prices, as long as he only uses the money he currently has. At the end of the last day, all remaining shares are converted back to cash.

Given the stock prices, determine the maximum amount of money Dongho can have after the D days.

Input

The first line contains three integers C, D, and M separated by spaces: the number of stocks, the number of trading days, and the initial amount of money.

1 <= C <= 50
2 <= D <= 10
1 <= M <= 200,000

Each of the next C lines contains D integers. The j-th integer on the i-th of these lines is the price of stock i on day j. Every stock price is between 1 and 1,000, inclusive.

Output

Print the maximum amount of money Dongho can have at the end.

Only data whose answer does not exceed 500,000 is given.

Examples1

Example 1
Input
```
2 3 10
10 15 15
13 11 20
```
Expected output
```
24
```