2598: 我真是High到不行啦
内存限制：32 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Dio如果吸收了二乔的血后加上大乔的身躯就能得到完全的力量!“我真是High到不行啦!”
现已知二乔的血被分布在N*M的网格中,每个格子有一个值代表此格子区域有多少二乔的血.Dio可以从任意一个格子开始出发,每次可以吸收当前他所在的格子的血,然后移动到上下左右方向的另一个格子上,这需要消耗1秒的时间。
问题在于他的对手乔太郎的速度很快,他可能被乔太郎追上然后被打死,但他可以发动“世界”这个能力来暂停时间,此能力最多暂停K秒,所以他每次发动“世界”最多经过K个格子然后停下来恢复时间,并吸收当前停下来的格子的二乔血(不能为空,但沿途经过的格子可以为空),由于他吸收血后身体更加渴望获得力量,所以下一次必须吸收比上一次吸收的血量多的血量,也就是说,如果他吸收的血量按顺序为a0,a1,…am,则有a0<a1<..<am。
现已知二乔的血被分布在N*M的网格中,每个格子有一个值代表此格子区域有多少二乔的血.Dio可以从任意一个格子开始出发,每次可以吸收当前他所在的格子的血,然后移动到上下左右方向的另一个格子上,这需要消耗1秒的时间。
问题在于他的对手乔太郎的速度很快,他可能被乔太郎追上然后被打死,但他可以发动“世界”这个能力来暂停时间,此能力最多暂停K秒,所以他每次发动“世界”最多经过K个格子然后停下来恢复时间,并吸收当前停下来的格子的二乔血(不能为空,但沿途经过的格子可以为空),由于他吸收血后身体更加渴望获得力量,所以下一次必须吸收比上一次吸收的血量多的血量,也就是说,如果他吸收的血量按顺序为a0,a1,…am,则有a0<a1<..<am。
输入
只有一个样例,第一行三个整数N M K(N*M<=1000,K<=N+M)
接下来N行,每行M个整数V代表每个格子的二乔血量(0<V<=10^6)
接下来N行,每行M个整数V代表每个格子的二乔血量(0<V<=10^6)
输出
Dio最多能吸收的血量
样例输入 复制
3 3 1
1 2 5
10 11 6
12 12 7
样例输出 复制
37