经典大原题

【问题描述】

共有$N*M$个景点，可以描述成一个$N*M$的矩形，每个景点有一个坐标$(x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M)$以及美观度$A[x][y]$和观赏所需的时间$B[x][y]$，从一个景点$(x1, y1)$走到另一个景点$(x2, y2)$需要时间为它们之间的曼哈顿距离：$|x1 - x2| +|y1 - y2|$。

要求观赏的景点的美观度严格上升，同时，旅游的总时间尽可能长。

【输入格式】

第一行输入两个整数N, M；

接下来N行每行M个整数，第x行第y个整数代表$A[x][y]$；

接下来N行每行M个整数，第x行第y个整数代表$B[x][y]$；

注意，有一些$A[x][y]=B[x][y]=0$，说明这个景点已经拆除，不能游览。

【输出格式】

输出一行代表最长的总时间。

【输入样例】

4 5

1 2 6 0 2

1 3 4 0 4

0 0 4 0 3

2 2 0 0 4

1 3 5 0 2

2 8 1 0 2

0 0 3 0 4

0 5 0 0 3

【输出样例】

39

【样例解释】

游览顺序为$(2,1)->(1,5)->(2,2)->(4,5)->(1,3)$

【数据范围】

对于30%的数据，$1≤N≤50,1≤M≤50;$

对于60%的数据，$1≤N≤300,1≤M≤300;$

对于100%的数据，$1≤N≤1000,1≤M≤1000,0≤A[x][y]≤1000000,0≤B[x][y]≤109$.

注意：卡常！写快读！写快读！写快读！