路径偏差

题目描述

有一个纵向 $H$ 格、横向 $W$ 格的网格。从上数第 $i$ 行、从左数第 $j$ 列的格子称为格子 $(i,j)$。

格子 $(i,j)$ 上写着 $2$ 个数 $A_{ij}, B_{ij}$。

高桥君首先对每个格子，将两个数中的一方涂成红色，另一方涂成蓝色。

然后，从格子 $(1,1)$ 移动到格子 $(H,W)$。高桥君每次行动可以从格子 $(i,j)$ 移动到格子 $(i+1,j)$ 或格子 $(i,j+1)$。不能进行超出网格范围的移动。

此时，对于移动路径（包含格子 $(1,1)$ 和格子 $(H,W)$），将「路径上格子中被涂成红色的数之和」与「路径上格子中被涂成蓝色的数之和」的差的绝对值称为 偏差。

高桥君希望通过合适地选择涂色方式和移动路径来减小偏差。

求偏差的最小值。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出偏差的最小值。

样例

2 2
1 2
3 4
3 4
2 1

0

选择如下涂色方式和移动路径时，路径上格子中被涂成红色的数之和为 $3+3+1=7$，被涂成蓝色的数之和为 $1+2+4=7$，可以将偏差减小到 $0$。

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

2

数据范围

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