问题 B: [STT2024WC+] 魔王军的扫荡
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
### 题目背景
七魔下昆仑后，重新为祸人间，同时组建起了势力庞大的魔王军。魔王军烧杀抢掠，遇村屠村，一个不留。
### 题目描述
人间平原的大小为 $n \times m$，每个地方有一个富有值 $a_{i,j}$ 和税费 $b_{i,j}$，富有值不为 $0$ 时，说明有可以掠劫的村子；税费不为 $0$ 时，说明要交过路费。每个村子只能被掠劫一次，获得 $a_{i,j}$ 的财富，过路费每次经过都必须交，失去 $b_{i,j}$ 的财富。
现有 $k$ 支魔王军要从 $(1,1)$，走到 $(n,m)$，完成急行军任务。由于军队管理严格，所以魔王军只能向下或向右走。魔王军希望最终总共的财富尽量多，如果不能获得财富，也希望花费尽量少。
输入
第一行三个正整数 $n,m,k$，分别表示人间平原的大小，魔王军的支数。
接下来 $n$ 行，每行 $m$ 个数 $a_{i,j}$。表示这个地区的财富值。
接下来 $n$ 行，每行 $m$ 个数 $b_{i,j}$。表示这个地区的税费。
接下来 $n$ 行，每行 $m$ 个数 $a_{i,j}$。表示这个地区的财富值。
接下来 $n$ 行，每行 $m$ 个数 $b_{i,j}$。表示这个地区的税费。
输出
一个整数，表示最多能获得的财富。
样例输入 复制
3 3 3
0 1 2
1 0 3
2 3 4
0 0 0
0 999 0
0 0 0样例输出 复制
16提示
### 样例 #2
#### 样例输入 #2
```
3 3 1
0 0 0
0 1 0
0 0 0
0 0 999
0 999 0
999 0 0
```
#### 样例输出 #2
```
-998
```
### 提示
**【样例 #1 解释】**
三支部队均从两边走，不交过路费，掠劫所有村子。
**【样例 #2 解释】**
必须交过路费，这时掠劫中间的村子获得一点财富来止血更优。
**【数据范围】**
对于 $40\%$ 的数据，$1 \leq n,m,k \leq 10$。
对于 $100\%$ 的数据，$1 \leq n,m,k \leq 50$，$0 \leq a_{i,j},b_{i,j} \leq 10^4$。