题目描述

随着旅游业的兴起，一家小型旅行社开始尝试通过机票预售来增加收入。该旅行社目前面临一个机会，可以预购未来几天内多个航班的机票，并在适当的时候将它们出售给游客。由于机票价格的波动，旅行社希望通过合理买卖机票来最大化利润。

这家旅行社了解到未来 $D$ 天内 $N$ 个航班的机票价格，并且它初始有 $M$ 元作为投资本金。旅行社可以在任何一天购买或出售任意数量的任意航班的机票，但每次交易的数量必须是整数张。当然，如果旅行社觉得行情不好，当天不交易也是允许的。

现在，这家旅行社希望你帮忙制定一个策略，使得在 $D$ 天后，他们能够获得最大的资金。

输入格式

第一行：三个整数 $N$、$D$ 和 $M$，分别表示航班的数量、天数和初始资金。

接下来 $N$ 行：每行 $D$ 个整数，代表一种航班未来 $D$ 天内的票价。

输出格式

输出一个整数，表示在 $D$ 天后旅行社通过买卖机票能够获得的最大资金。

请注意，测试数据保证 $D$ 天后旅行社的最大资金数不会超过 $500000$。

样例

输入

2 3 10
10 15 16
13 11 18

输出

22

输入

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

输出

52

数据范围

对于 $100\%$ 的数据，保证 $2 \le N \le 50$，$2 \le D \le 10$，$1 \le M \le 200000$，机票价格均在 $[1, 1000]$ 的范围内。