题目描述

小林偶然获得了一种预知未来的能力，他能看到未来 $T$ 天内 $N$ 种商品每天的售价。每种商品的买入价和卖出价相同，均为当日牌价。

每天，小林可以进行以下两种操作任意多次：

1. 若手中金币足够，以当日牌价买入任意一种商品；
2. 以当日牌价卖出手中持有的任意一件商品。

当天卖出所得的金币可以立刻再用于买入，当天买入的商品也可以当天卖出。当然，一直持有商品不卖也完全可以。

$T$ 天后能力消失，小林必须在最后一天将所有商品卖出换回金币。

小林初始有 $M$ 枚金币，求能力消失后他最多能拥有多少金币。

输入格式

第一行三个正整数 $T, N, M$，相邻两数以空格分隔，分别表示天数、商品种类数和初始金币数。

接下来 $T$ 行，每行 $N$ 个正整数，相邻两数以空格分隔。第 $i$ 行第 $j$ 个数 $P_{i,j}$ 表示第 $i$ 天第 $j$ 种商品的牌价。

输出格式

一行一个正整数，表示小林最多能拥有的金币数。

样例

6 1 100
50
20
25
20
25
50

305

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

217

提示

样例 1 说明

只有一种商品，价格序列为 $50, 20, 25, 20, 25, 50$。

最优策略：第 2 天用 100 枚金币买入 5 件（单价20）；第 3 天全部卖出得 125 枚；第 4 天买入 6 件（单价20，花费120，余5枚）；第 5 天全部卖出得 150 枚，加上余下5枚共 155 枚；第 5 天再买入6件（单价25，花费150，余5枚）；第 6 天全部卖出得 300 枚，加上余下5枚共 305 枚。

样例 2 说明

最优策略：第 1 天买入 10 件商品 1（花费100）；第 2 天卖出得 150 枚，买入 8 件商品 2（花费136）和 1 件商品 3（花费13），余 1 枚；第 3 天卖出全部得 216 枚，加上余下1枚共 217 枚。

数据规模与约定

对于 $10\%$ 的数据，$T = 1$。

对于 $30\%$ 的数据，$T \leq 4, N \leq 4, M \leq 100$，所有价格 $10 \leq P_{i,j} \leq 100$。

另有 $15\%$ 的数据，$T \leq 100, N = 1$。

另有 $15\%$ 的数据，$T = 2, N \leq 100$。

对于 $100\%$ 的数据，$T \leq 100, N \leq 100, M \leq 10^3$，所有价格 $1 \leq P_{i,j} \leq 10^4$，数据保证任意时刻金币数不超过 $10^4$。