题目描述

有一个 $H$ 行 $W$ 列的棋盘，第 $i$ 行第 $j$ 列的棋盘格记为 $(i,j)$。每个格子中都写了两个数，$(i,j)$ 中写有整数 $A_{i,j}$ 和 $B_{i,j}$。

高桥君首先对每个格子里的两个数染色：一个涂成红色，另一个涂成蓝色。

染色完成后，高桥君从左上角 $(1,1)$ 出发，每次可以向右或向下走一格，直到到达右下角 $(H,W)$。途中经过的所有格子（包括起点和终点）中红色数字之和记为 $R$，蓝色数字之和记为 $B$。

通过适当的染色以及选取合适的路径，高桥君想要 $R$ 和 $B$ 之差的绝对值尽可能的小。问 $|R-B|$ 的最小值是多少？

输入格式

输入共 $2H+1$ 行。

第 $1$ 行，两个正整数 $H,W$。

第 $2$ 到 $H+1$ 行，每行 $W$ 个整数，第 $i+1$ 行第 $j$ 个数为 $A_{i,j}$。

第 $H+2$ 到 $2H+1$ 行，每行 $W$ 个整数，第 $i+H+1$ 行第 $j$ 个数为 $B_{i,j}$。

输出格式

输出 $|R-B|$ 的最小值。

说明与提示

样例 $1$ 说明：

如下图染色和选择路径，路上红色数总和 $R=3+3+1=7$，蓝色数总和 $B=1+2+4=7$，所以 $|R-B|$ 的最小值是 $0$。

来源

浩轩OJ 4391 · 原题图片

数据范围与约定

$2\le H,W\le80$，$0\le A_{i,j},B_{i,j}\le80$。

可见测试数据

输入数据 1

2 2
1 2
3 4
3 4
2 1

输出数据 1

0

输入数据 2

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

输出数据 2

2

输入数据 3

2 2
5 75
64 15
3 24
61 6

输出数据 3

4