E - 平衡路径

得分：500分

题目描述

给定一个大小为$H\times W$的格子。$(i,j)$表示在第$i$行，第$j$列的格子。

每个格子上都有两个数字$A_{ij}$和$B_{ij}$。

首先，对于每个格子，Takahashi将其中一个数字涂成红色，另一个涂成蓝色。

然后，他从方格$(1,1)$移动到方格$(H,W)$。在一次移动中，他可以从一个方格$(i,j)$移动到相邻的方格$(i+1,j)$或者$(i,j+1)$。他不能离开格子。

定义不平衡度为沿着Takahashi的路径上所有方格上红色数字之和与蓝色数字之和的绝对差。

Takahashi希望通过合适的涂色和移动使得不平衡度尽量小。

你需要找到可能的最小不平衡度。

约束

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

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