Migrated from Lutece 2557 平面图最大流

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个 $n\times m$ 的网格图，左上角为点 $(1,1)$，右下角为点 $(n,m)$，点 $(x,y)$ 与在 $n\times m$ 网格内的点 $(x,y+1),(x+1,y),(x+1,y+1)$ 连有给定流量上限的边，求从点 $(1,1)$ 到点 $(n,m)$ 的最大流。

Input

第一行两个整数 $n,m$，表示网格图的大小。

接下来 $n$ 行，每行 $m-1$ 个整数，第 $x$ 行第 $y$ 个整数表示 $(x,y)$ 与 $(x,y+1)$ 之间边的流量上限。

接下来 $n-1$ 行，每行 $m$ 个整数，第 $x$ 行第 $y$ 个整数表示 $(x,y)$ 与 $(x+1,y)$ 之间边的流量上限。

接下来 $n-1$ 行，每行 $m-1$ 个整数，第 $x$ 行第 $y$ 个整数表示 $(x,y)$ 与 $(x+1,y+1)$ 之间边的流量上限。

Output

一个整数，表示从点 $(1,1)$ 到点 $(n,m)$ 的最大流。

Samples

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

14

Constraints

$3\le n,m\le 1000$ 所有流量上限为不超过 $10^6$ 的正整数

Resources

2021 UESTC ICPC Training for Graph