P12214 [蓝桥杯 2023 国 Python B] 贸易航线

小蓝要带领一支船队依次经过 $n$ 个地点。小蓝的船上可以携带 $k$ 单位的商品，商品共有 $m$ 种，在每个地点的价格各不相同，部分商品在部分地区无法交易。 一开始小蓝的船是空的，小蓝可以在每个地点任意地买入各种商品，然后在之后经过的地点卖出。小蓝的钱很多，你可以认为小蓝买入商品时只会受到船队的容量的限制。 问小蓝到达终点时的最大收益是多少。

输入的第一行包含三个整数 $n, m, k$，相邻的整数之间使用一个空格分隔。 接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数 $P_{i,j}$ 表示在第 $i$ 个地点第 $j$ 种商品的价格。特别地，值为 $-1$ 表示该商品在这个地区无法交易。

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

### 评测用例规模与约定 - 对于 $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$。