#CSPJ2019C. 纪念品 (Souvenir)

纪念品 (Souvenir)

Description

Xiaowei suddenly acquires a superpower. He knows the daily prices of NN souvenirs for the next TT 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:

  1. Choose a souvenir. If he has enough gold coins with him, buy the souvenir at its price for that day.
  2. 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 TT days, Xiaowei’s superpower will disappear. Therefore, he will sell all the souvenirs he still has on the TT-th day.

Currently, Xiaowei has MM 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 TT, NN and MM - the number of days for which Xiaowei knows souvenir prices, the number of souvenirs, and the number of gold coins that Xiaowei currenly has.

ii-th of the next TT lines contains NN positive integers Pi,1,Pi,2,...,Pi,N,P_{i, 1}, P_{i, 2}, ..., P_{i, N}, where Pi,jP_{i, j} denotes the price of the jj-th souvenir on the ii-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 100100 gold coins to buy 55 units of souvenir 11.
Sell all the 55 units of souvenir 11 on the third day and get 125125 gold coins.
Buy 66 units of souvenir 11 on the fourth day. 55 gold coins are left.
On the sixth day, sell all souvenirs for 300300 gold coins. On the fourth day there were 55 gold coins remaining, so now there are 305305 gold coins remaining.

After the superpower disappears, Xiaowei has 305305 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 1010 units of souvenir 11.
Sell all the units of souvenir 11 on the next day and get 150150 gold coins. Buy 88 units of souvenir 22 and 11 unit of souvenir 33. 11 gold coin is remaining.
On the third day, sell all souvenirs and get 216216 gold coins. On the second day, there was 11 gold coin left, so in total there are 217217 gold coins left.

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

Constraints

For 10%10\% of the data, T=1T = 1.
For 30%30\% of the data, T4,N4,M100,10Pi,j1001T \le 4, N \le 4, M \le 100, 10 \le P_{i, j} \le 1001.
For another 15%15\% of the data, T100,N=1T \le 100, N = 1.
For another 15%15\% of the data, T=2,N100T = 2, N \le 100.
For 100%100\% of the data, T100,N100,M103,1Pi,j104T \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 10410^4.