题目描述

一家旅行社知道未来 $d$ 天内 $n$ 种机票每天的价格，开始时有 $m$ 元资金。

在第 $i$ 天，旅行社可以购买任意种类、任意非负整数张机票，但总费用不能超过当前资金。当天买入的机票会在第 $i+1$ 天按该种机票当天的价格全部卖出，之后再决定下一天购买哪些机票。资金也可以全部或部分保留，不用于购买。

请计算第 $d$ 天卖出此前购买的机票后，旅行社最多可以拥有多少资金。

输入格式

第一行包含三个整数 $n,d,m$，分别表示机票种类数、天数和初始资金。

接下来 $n$ 行，每行包含 $d$ 个整数。第 $i$ 行第 $j$ 个整数表示第 $i$ 种机票在第 $j$ 天的价格。

输出格式

输出一个整数，表示第 $d$ 天最多可以拥有的资金。

样例

2 3 10
10 15 16
13 11 18

22

3 3 50
862 270 15
26 27 28
983 997 681

52

数据范围与提示

• $2 \le n \le 50$
• $2 \le d \le 10$
• $1 \le m \le 200000$
• 每张机票每天的价格均为 $1$ 到 $1000$
• 保证答案不超过 $500000$