题目描述

We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i,j)$ denote the square at the $i$-th row from the top and the $j$-th column from the left.

The square $(i, j)$ has two numbers $A_{ij}$ and $B_{ij}$ written on it.

First, for each square, Takahashi paints one of the written numbers red and the other blue.

Then, he travels from the square $(1, 1)$ to the square $(H, W)$. In one move, he can move from a square $(i, j)$ to the square $(i+1, j)$ or the square $(i, j+1)$. He must not leave the grid.

Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares $(1, 1)$ and $(H, W)$.

Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.

Find the minimum unbalancedness possible.

我们有一个横向有 $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}$
$:$
$A_{H1}$ $A_{H2}$ $\ldots$ $A_{HW}$
$B_{11}$ $B_{12}$ $\ldots$ $B_{1W}$
$:$
$B_{H1}$ $B_{H2}$ $\ldots$ $B_{HW}$

输出格式

打印可能的最小不平衡度。

样例 #1

样例输入 #1

2 2
1 2
3 4
3 4
2 1

样例输出 #1

0

样例 #2

样例输入 #2

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

样例输出 #2

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