# #CSPJ2019C. 纪念品 (Souvenir)

# 纪念品 (Souvenir)

## Description

Xiaowei suddenly acquires a superpower. He knows the daily prices of $N$ souvenirs for the next $T$ days. The price of a souvenir refers to the number of gold coins required to buy the souvenir or the number of gold coins that can be earned by selling a souvenir.

Every day, Xiaowei can carry out the following two types of transactions any number of times:

- Choose a souvenir. If he has enough gold coins with him, buy the souvenir at its price for that day.
- Sell any souvenir he has and earn gold coins equal to the price of the souvenir for that day.

The gold coins earned by selling souvenirs on a day can be used to buy souvenirs on the same day too. Similarly, souvenirs purchased on a day can also be sold for gold coins on the same day.

After $T$ days, Xiaowei’s superpower will disappear. Therefore, he will sell all the souvenirs he still has on the $T$-th day.

Currently, Xiaowei has $M$ gold coins, and he wants to have as many gold coins as possible after the superpower disappears. What is the maximum number of gold coins he can have?

## Input Format

The first line contains three positive integers $T$, $N$ and $M$ - the number of days for which Xiaowei knows souvenir prices, the number of souvenirs, and the number of gold coins that Xiaowei currenly has.

$i$-th of the next $T$ lines contains $N$ positive integers $P_{i, 1}, P_{i, 2}, ..., P_{i, N},$ where $P_{i, j}$ denotes the price of the $j$-th souvenir on the $i$-th day.

## Output Format

Print one line containing a positive integer denoting the maximum number of gold coins Xiaowei can have after his superpower disappears.

```
6 1 100
50
20
25
20
25
50
```

```
305
```

The best strategy is:

On the second day, spend all $100$ gold coins to buy $5$ units of souvenir $1$.

Sell all the $5$ units of souvenir $1$ on the third day and get $125$ gold coins.

Buy $6$ units of souvenir $1$ on the fourth day. $5$ gold coins are left.

On the sixth day, sell all souvenirs for $300$ gold coins. On the fourth day there were $5$ gold coins remaining, so now there are $305$ gold coins remaining.

After the superpower disappears, Xiaowei has $305$ gold coins, which is the maximum possible.

```
3 3 100
10 20 15
15 17 13
15 25 16
```

```
217
```

The best strategy is:

On the first day, spend all the gold coins to buy $10$ units of souvenir $1$.

Sell all the units of souvenir $1$ on the next day and get $150$ gold coins. Buy $8$ units of souvenir $2$ and $1$ unit of souvenir $3$. $1$ gold coin is remaining.

On the third day, sell all souvenirs and get $216$ gold coins. On the second day, there was $1$ gold coin left, so in total there are $217$ gold coins left.

After the superpower disappears, Xiaowei has $217$ gold coins, which is the maximum possible.

## Constraints

For $10\%$ of the data, $T = 1$.

For $30\%$ of the data, $T \le 4, N \le 4, M \le 100, 10 \le P_{i, j} \le 1001$.

For another $15\%$ of the data, $T \le 100, N = 1$.

For another $15\%$ of the data, $T = 2, N \le 100$.

For $100\%$ of the data, $T \le 100, N \le 100, M \le 10^3, 1 \le P_{i, j} \le 10^4$. It is guaranteed that at any time, the number of gold coins that Xiaowei has can't exceed $10^4$.