← 返回题目列表

AtCoder · abc147_e

E. 平衡路径

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。

广场 (i, j) 有两个数字 上面写着 A_{ij} 和 B_{ij} 。

首先,对于每个方格,高桥将其中一个书写数字涂成红色,另一个涂成蓝色。

然后,他从广场出发 (1, 1) 到广场 (H, W)。他可以一步从一个方格移动 (i, j) 到广场 (i+1, j) 或正方形 (i, j+1)。他不能离开网格。

让 不平衡 是沿着高桥路径的方格上写的红色数字之和与蓝色数字之和的绝对差,包括方格 (1, 1) 和 (H, W).

高桥希望通过适当地绘制网格并在其上行驶来使不平衡性尽可能小。

找出可能的最小不平衡度。

约束

  • 2 \leq H \leq 80
  • 2 \leq W \leq 80
  • 0 \leq A_{ij} \leq 80
  • 0 \leq B_{ij} \leq 80
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}

输出

打印可能的最小不平衡度。


示例输入 1

2 2
1 2
3 4
3 4
2 1

示例输出 1

0

如下图所示,通过绘制网格并在其上行驶,红色数字之和与蓝色数字之和为 3+3+1=7 和 1+2+4=7分别为 0.

Figure


示例输入 2

2 3
1 10 80
80 10 1
1 2 3
4 5 6

示例输出 2

2