题目描述

我们有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 列的方格。

方格 $(i, j)$ 上有两个数 $A_{ij}$ 和 $B_{ij}$。

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

然后，他从方格 $(1, 1)$ 出发，前往方格 $(H, W)$。每次移动，他可以从方格 $(i, j)$ 移动到方格 $(i+1, j)$ 或者方格 $(i, j+1)$。他不能离开网格。

将“不平衡度”定义为高桥路径上的方格中红色数字的和与蓝色数字的和的绝对差。

高桥希望通过适当地上色并在网格上行走，使得不平衡度尽可能小。

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

约束条件

• $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$。

示例输入 2

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

示例输出 2

2