纪念品（souvenir）

程序文件名：souvenir.cpp / souvenir.c / souvenir.pas 输入文件名：souvenir.in 输出文件名：souvenir.out

问题描述

小伟突然获得一种超能力，他知道未来 (T) 天内，(N) 种纪念品每天的价格。

某个纪念品的价格，是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

1. 任选一种纪念品，若手上有足够的金币，就以当日价格购买一个该纪念品。
2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币，可以立即用于购买纪念品；当日购买的纪念品，也可以当日卖出换回金币。当然，也可以一直持有纪念品。

(T) 天之后，小伟的超能力消失。因此，他一定会在第 (T) 天卖出所有纪念品，换回金币。

小伟现在有 (M) 枚金币，他想在超能力消失后拥有尽可能多的金币。

输入格式

输入文件名为 souvenir.in。

第一行包含三个正整数 (T,N,M)，相邻两数之间以一个空格分隔，分别表示：

• (T)：未来的天数。
• (N)：纪念品的种类数。
• (M)：小伟现在拥有的金币数量。

接下来 (T) 行，每行包含 (N) 个正整数，相邻两数之间以一个空格分隔。

第 (i) 行的 (N) 个正整数分别为：

其中，(P_{i,j}) 表示第 (i) 天第 (j) 种纪念品的价格。

输出格式

输出文件名为 souvenir.out。

输出一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

输入输出样例 1

输入

6 1 100
50
20
25
20
25
50

输出

305

样例说明

最佳策略是：

1. 第 2 天，花光所有 100 枚金币，买入 5 个纪念品 1。
2. 第 3 天，卖出 5 个纪念品 1，获得 125 枚金币。
3. 第 4 天，买入 6 个纪念品 1，剩余 5 枚金币。
4. 第 6 天，卖出所有纪念品，换回 300 枚金币，加上第 4 天剩余的 5 枚金币，共有 305 枚金币。

超能力消失后，小伟最多拥有 305 枚金币。

样例文件见选手目录下的 souvenir/souvenir1.in 和 souvenir/souvenir1.ans。

输入输出样例 2

输入

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

输出

217

样例说明

最佳策略是：

1. 第 1 天，花光所有金币，买入 10 个纪念品 1。

2. 第 2 天，卖出全部纪念品 1，得到 150 枚金币；然后买入 8 个纪念品 2 和 1 个纪念品 3，剩余 1 枚金币。

3. 第 3 天，卖出所有纪念品，换回：

   $$8\times25+1\times16=216$$

   枚金币，加上第 2 天剩余的 1 枚金币，共有 217 枚金币。

超能力消失后，小伟最多拥有 217 枚金币。

样例文件见选手目录下的 souvenir/souvenir2.in 和 souvenir/souvenir2.ans。

输入输出样例 3

见选手目录下的 souvenir/souvenir3.in 和 souvenir/souvenir3.ans。

数据规模与约定

数据保证：任意时刻，小伟手上的金币数不可能超过 (10^4)。