Invest Master

Interview

Time limit2sMemory limit512 MB

Summary

Given predicted prices for n stocks over d days, buy and sell units to maximize cash on the last day, with no fees and no intraday price change.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Implementation, Math
Solved: No attempts yet

Problem

After years of research, Ikuta has gained the power to see the future! The time and money he spent on this research were enormous, but the day he is rewarded has finally come. To start by recovering his money, Ikuta decides to begin investing in stocks.

Ikuta currently owns no stocks at all and has $x$ yen. The stocks he has chosen as investment targets are of $n$ kinds, and for them he has succeeded in predicting the stock prices for $d$ days starting today. As a result, it turned out that, surprisingly, there is no intraday price fluctuation at all during the $d$ days starting today. That is, when today is day 1, he knows the price $p_{i,j}$ yen of stock $j$ ( $1 \leq j \leq n$ ) on day $i$ ( $1 \leq i \leq d$ ). Ikuta can freely buy and sell stocks on each day. In other words, at any point he can perform the following operations (buy and sell) in any order and any number of times. However, before and after each operation, his cash and the number of stock units he holds must be nonnegative integers.

Buy: on day $i$ , choose one stock kind $j$ ( $1 \leq j \leq n$ ), pay $p_{i,j}$ yen of cash, and obtain 1 unit of stock $j$ .
Sell: on day $i$ , choose one stock kind $j$ ( $1 \leq j \leq n$ ), give up 1 unit of stock $j$ , and obtain $p_{i,j}$ yen.

(While he was absorbed in research, the securities trading system made great progress, and transaction fees are no longer charged.)

Ikuta studied information science at university, but after devoting himself to future prediction research, he forgot everything he learned at university. Please write a program that maximizes his cash on the final day on his behalf.

Input

The input is given in the following format.

$n$ $d$ $x$

$p_{1,1}$ ... $p_{1,n}$

...

$p_{d,1}$ ... $p_{d,n}$

$n$ : the number of stock kinds
$d$ : the number of days
$x$ : cash on day 1
$p_{i,j}$ : the price of stock $j$ on day $i$ (today is day 1)

Output

Print the cash on the final day when investing optimally, on one line.

Constraints

Each variable in the input is an integer satisfying the following constraints.

$1 \leq n \leq 10$
$1 \leq d \leq 10$
$1 \leq x, p_{i,j} \leq 10^5$
The cash on the final day is guaranteed to be at most $10^5$ .

Examples4

Example 1
Input
```
2 2 5
3 2
5 4
```
Expected output
```
9
```
Example 2
Input
```
1 2 5
6
10000
```
Expected output
```
5
```
Example 3
Input
```
2 3 5
4 5
6 3
8 5
```
Expected output
```
11
```
Example 4
Input
```
3 3 10
10 9 6
8 7 3
7 5 1
```
Expected output
```
10
```