버스 여행

격자 모양으로 잘 정돈된 어느 도시가 있다. 이 도시에는 동-서 방향 거리 $n$개와 남-북 방향 거리 $m$개가 있으며, 서로 인접한 평행한 거리는 정확히 100m 간격으로 떨어져 있다.

관광 명소는 항상 두 거리가 만나는 교차로에 위치한다. $i$번 동-서 거리와 $j$번 남-북 거리가 만나는 교차로를 $(i, j)$로 나타내며, 그곳에 관광 명소가 있다면 건설 시기 $a_{i,j}$와 매력도 $c_{i,j}$가 정해져 있다.

재현이는 관광 명소 몇 곳을 정해진 순서로 방문하는 버스 여행을 계획하려 하며, 얻는 매력도의 총합을 최대로 만들고 싶다. 규칙은 다음과 같다.

• 이번 여행의 테마는 도시의 역사이므로, 방문하는 관광 명소의 건설 시기는 엄격히 증가해야 한다. 즉, 바로 앞에 방문한 명소보다 건설 시기가 반드시 더 커야 하며, 같아서는 안 된다.
• 관광 명소를 방문하면 그 명소의 매력도만큼 총합이 늘어난다.
• 버스가 두 관광 명소 사이를 이동하는 동안에도 승객들이 경치를 즐기므로, 이동 거리 100m마다 매력도가 1씩 늘어난다. 버스는 항상 최단 경로로 이동하므로, 두 명소 $(i_1, j_1)$과 $(i_2, j_2)$ 사이를 이동하며 얻는 매력도는 $|i_1 - i_2| + |j_1 - j_2|$이다.
• 이동 도중 단지 지나치기만 한 관광 명소는 방문한 것으로 치지 않는다.

여행은 아무 관광 명소에서나 시작해 아무 관광 명소에서나 끝낼 수 있고, 중간에 여러 명소를 들를 수도 있으며, 단 하나의 명소만 방문해도 된다. 가능한 모든 여행 계획 중에서 얻을 수 있는 매력도 총합의 최댓값을 구하여라.

첫째 줄에 동-서 방향 거리의 개수 $n$과 남-북 방향 거리의 개수 $m$이 주어진다. ($2 \le n, m \le 1000$)

다음 $n$개의 줄에는 각 교차로의 건설 시기가 주어진다. 그중 $i$번째 줄에는 $m$개의 정수 $a_{i,j}$ ($0 \le a_{i,j} \le 10^6$)가 주어지며, 이는 $(i, j)$ 교차로의 값이다. $a_{i,j} = 0$이면 그 교차로에는 관광 명소가 없다는 뜻이다. 관광 명소는 적어도 하나 존재한다.

이어서 $n$개의 줄에는 각 교차로의 매력도가 주어진다. 그중 $i$번째 줄에는 $m$개의 정수 $c_{i,j}$ ($0 \le c_{i,j} \le 10^9$)가 주어지며, 이는 $(i, j)$ 교차로에 있는 관광 명소의 매력도이다. 해당 교차로에 관광 명소가 없다면 $c_{i,j} = 0$임이 보장된다.

가능한 여행 계획 중 얻을 수 있는 매력도 총합의 최댓값을 한 줄에 출력한다.

아래는 첫 번째 예제에 대한 최적의 여행 계획이다. 재현이는 $(2, 1) \to (1, 5) \to (2, 2) \to (4, 5) \to (1, 3)$ 순서로 관광 명소를 방문한다. 방문한 명소들의 건설 시기는 각각 $1, 2, 3, 4, 6$으로 엄격히 증가한다.

방문한 명소들의 매력도 합은 $2 + 2 + 8 + 3 + 5 = 20$이고, 이동하며 얻은 매력도 합은 $5 + 4 + 5 + 5 = 19$이다. 따라서 총 매력도는 $39$이다.