AT_abc147_e [ABC147E] Balanced Path

题目描述

有一个高为 $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)$），定义偏差为「路径上格子红色数字之和」与「路径上格子蓝色数字之和」的差的绝对值。

高桥君希望通过恰当选择涂色方案和移动路径，使偏差尽可能小。

请求出偏差的最小值。

输入格式

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

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

输出格式

请输出偏差的最小值。

样例 1

输入

2 2
1 2
3 4
3 4
2 1

输出

0

样例 2

输入

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$
• 输入中的所有值均为整数。

样例解释 1

按照下图的涂色方案和移动路径选择，路径上的红色数字之和为 $3+3+1=7$，蓝色数字之和为 $1+2+4=7$，可以将偏差控制为 $0$。