Description

跳蚤国广袤的国土可以看做一个\( n \)行\( m \)列的矩阵，每个格子代表了一个地区，我们可以把第\( i \)行第\( j \)列的格子所代表的地区称作\( (i,j) \)。地区\( (i,j) \)的跳蚤数目为\( a[i][j] \)，吸引度为\( b[i][j] \)。现在，无聊的跳蚤国王要对其中一些地区进行检阅，为了保持心灵的舒畅，跳蚤国王要求受阅地区的跳蚤数目依次递增。如果某些地区没有跳蚤,即 \( a[i][j] = 0 \)，那么跳蚤国王不会对这些地区进行检阅。

也就是说，你需要找到一个长度为\( k (1 ≤ k ≤ n × m) \)的路径\( (xi,yi) \)，使得：

对于 \( 1 ≤ i ≤ k \)，都有 \( a[x_i][y_i] > 0 \)。

对于 \( 1 ≤ i < k \)，都有 \( a[x_i][y_i] < a[x_{i+1}][y_{i+1}] \)。

你的任务是要最大化\( \sum_{i=1}^k b[x_i][y_i] + \sum_{i=1}^{k-1} {|x_{i+1} - x_i | + |y_{i+1} - y_i |}\)。

Format

Input

第一行2个整数\(n, m\)。

接下来有\(n\)行，每行\(m\)个整数，表示\(a\)数组。
接下来有\(n\)行，每行\(m\)个整数，表示\(b\)数组。

Output

一行一个整数表示答案。

Sample 1

Input

3 3
0 6 8
1 6 1
0 6 8
0 1 2
3 4 5
0 6 7 

Output

21

Limitation

2s, 512MiB for each test case.

Hint

样例解释

最优路径(2, 3)(3, 2)(3, 3)

最优答案\( 5 + 6 + 7 + |3 - 2| + |2 - 3| + |3 - 3| + |3 - 2| = 21\)。

更多输入输出样例请见选手下发文件夹。

数据范围与约定

对于所有数据，\(1≤ n ,m ≤ 2×10^3, 0 ≤ ai ≤ 10^6, 0 ≤ bi ≤ 10^6\)。

保证至少存在一个地区 \(a[i][j] > 0\)，所有 \(a[i][j] = 0\)的地区满足 \(b[i][j] = 0\)。

测试点编号	\(n,m\)	特殊性质
1~4	\(≤3\)	无
5~8	\(≤10^2\)	无
7~12	\(≤10^3\)	\(a[i][j] = i\)
13~16	\(≤10^3\)	无
17~20	\(≤2×10^3\)	无

Source

CSP2019第二轮测试模拟题（一）