问题描述

小蓝要带领一支船队依次经过 $n$ 个地点。小蓝的船上可以携带 $k$ 单位的商品，商品共有 $m$ 种，在每个地点的价格各不相同，部分商品在部分地区无法交易。

一开始小蓝的船是空的，小蓝可以在每个地点任意地买入各种商品，然后在之后经过的地点卖出。小蓝的钱很多，你可以认为小蓝买入商品时只会受到船队的容量的限制 。

问小蓝到达终点时的最大收益是多少。

输入格式

输入的第一行包含三个整数 $n,m,k$，相邻的整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数 $P_{i,j}$​ 表示在第 $i$ 个地点第 $j$ 种商品的价格。特别地，值为 -1 表示该商品在这个地区无法交易。

输出格式

输出一行包含一个整数表示答案。

样例

7 4 4
1 2 3 6
-1 2 3 4
-1 2 4 4
3 3 2 2
2 5 3 1
1 3 3 2
1 2 4 2

24

评测用例规模与约定

对于 $20\%$ 的评测用例， $n≤300$， $m≤3$，$k≤10$；

对于 $40\%$ 的评测用例，$n≤2000$，$m≤4$，$k≤50$；

对于所有评测用例， $1≤n≤10^5$，$1≤m≤10$，$1≤k≤100$，$1≤P_{i,j}≤10^9$。