题目描述

縦 $H$ マス、横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼びます。

マス $(i,j)$ には $2$ つの数 $A_{ij},\ B_{ij}$ が書かれています。

高橋君はまず各マスについて、$2$ つの数の一方を赤く、もう一方を青く塗ります。

そのあと、マス $(1,1)$ からマス $(H,W)$ まで移動します。高橋君は $1$ 回の行動でマス $(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}$

输出格式

偏りの最小値を求めよ。

题目大意

题目描述

高桥君有一个 $H$ 行 $W$ 列的棋盘，第 $i$ 行 $j$ 列记为 ( $i$ , $j$ ),每个格子里有两个整数， $a_{i,j}$ 和 $b_{i,j}$。

高桥君从( 1,1 )出发要走到( $H$ , $W$ )。每一次只能向左或向下走一格，每一次走过的方格，高桥君会把它上面的数一个染成红色，一个染成蓝色，求做过路径中红色数字的总和减蓝色数字总和的绝对值的最小值。

输入格式

第一行两个整数 $H$ , $W$ 。

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

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

输出格式

一行一个整数表示答案

2 2
1 2
3 4
3 4
2 1

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$
• 入力中のすべての値は整数である。

Sample Explanation 1

次のような塗り分けと移動経路を選択すると、経路上のマスの赤く塗られた数の和は $3+3+1=7$、経路上のマスの青く塗られた数の和は $1+2+4=7$ となり、偏りを $0$ にできます。