题目描述

小蓝要带领一支船队依次经过 $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 \leq 300$，$m \leq 3$，$k \leq 10$；
• 对于 $40\%$ 的评测用例，$n \leq 2000$，$m \leq 4$，$k \leq 50$；
• 对于所有评测用例，$1 \leq n \leq 10^5$，$1 \leq m \leq 10$，$1 \leq k \leq 100$，$1 \leq P_{i,j} \leq 10^9$。