题目描述

小 A 有一块 $n \times m$ 的田地，今年大丰收，他喜欢在其中散步。每块田地都有一定数量的小麦，且都被小 A 涂成了黑色或白色。坐标为 $(i,j)$ 的那块田地有 $a_{i,j}$ 千克的小麦，颜色为 $b_{i,j}$。当 $b_{i,j} = 0$ 时，这块地是黑色的，当 $b_{i,j} = 1$ 时，这块地是白色的。

他要从 $(1,1)$ 出发散步到 $(n,m)$。散步时，他只能往右或往下走。

当他散步到 $(x,y)$ 时：

• $b_{x,y} = 0$

你可以收到你经过的上一个黑色格子上的小麦。如果这是你经过的第一个黑色格子，你不能收到小麦。

• $b_{x,y} = 1$

如果你经过的上一个格子为白色，你将收到本格子上的小麦。否则，你不能收到小麦。当然，如果你位于 $(1,1)$，你一定不能收到小麦。

现在小 A 想知道，他最多能收到多少小麦。

输入格式

第一行两个数，$n$ 和 $m$。

后面 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 个数代表 $a_{i,j}$。

后面跟着 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 个数代表 $b_{i,j}$。

输出格式

一个数，代表最多能采到小麦的总数。

3 5
1 2 3 4 5
2 2 1 3 2
4 5 6 4 1
0 0 1 0 1
1 1 0 0 0
1 0 1 0 1

10

2 2
2 5 
7 8
0 1
0 1

8

1 3
5 4 3
0 0 1

5

提示

本题采用捆绑测试。

• Subtask 1（25pts）：$1 \le n \times m \le 10$。

• Subtask 2（25pts）：$1 \le n \times m \le 1000$。

• Subtask 3（10pts）：$b_{i,j} = 0$。

• Subtask 4（40pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 10^3,1 \le a_{i,j} \le 10^6,b_{i,j} \in \{0,1\}$。