맨후탄에서 태우고 털자

세상에는 화가 나면 불을 지르는 사람과 강도짓을 하는 사람, 두 부류가 있다고 한다. 그러나 프로그래머는 세 번째 부류가 있다는 것을 안다. 불을 지르기도 하고 강도짓도 해서 화를 풀어내는 사람들이다.

Bob은 Manhootan에 산다. Manhootan은 $n$개의 행과 $m$개의 열로 이루어진 격자 도시이며, 블록은 모두 $n \times m$개이다. 행은 북에서 남으로 0부터 $n-1$까지, 열은 서에서 동으로 0부터 $m-1$까지 번호가 매겨진다. $i$번째 행의 $j$번째 블록의 가치는 $A_{ij}$이다.

첫 번째 행 앞, 인접한 두 행 사이, 마지막 행 뒤에는 동서 방향 도로가 하나씩 있다. 이 $n+1$개의 도로는 북에서 남으로 0부터 $n$까지 번호가 매겨진다. 마찬가지로 첫 번째 열 앞, 인접한 두 열 사이, 마지막 열 뒤에는 남북 방향 도로가 있고, 이 $m+1$개의 도로는 서에서 동으로 0부터 $m$까지 번호가 매겨진다. 인접한 두 블록 사이에 있는 도로의 부분을 도로 구간이라고 한다. 각 동서 도로에는 서에서 동으로 0부터 $m-1$까지 번호가 매겨진 도로 구간이 $m$개 있고, 각 남북 도로에는 북에서 남으로 0부터 $n-1$까지 번호가 매겨진 도로 구간이 $n$개 있다. $i$번째 동서 도로의 $j$번째 도로 구간을 지나는 데 $H_{ij}$가 들고, $i$번째 남북 도로의 $j$번째 도로 구간을 지나는 데 $V_{ij}$가 든다.

$i$번째 동서 도로와 $j$번째 남북 도로가 만나는 교차로를 $T(i, j)$라고 하자. Bob은 $T(0, 0)$에서 출발해 동쪽과 남쪽으로만 이동하여 $T(n, m)$에 도착한다. 그런 다음 서쪽과 북쪽으로만 이동하여 $T(0, 0)$으로 돌아온다. Bob은 차의 연료 탱크에 구멍을 내서 지나는 도로마다 연료가 새게 한다. 새어 나온 연료에 불을 붙이면 그 도로들이 불에 탄다. 불타는 도로를 건너지 않고는 Manhootan 바깥으로 나갈 수 없는 블록은 모두 Bob이 턴다.

그림은 가능한 계획의 하나이다. 여러분은 Bob처럼 행동하면 안 되지만, Bob을 도와 가장 이익이 큰 방화와 강도 계획을 찾을 수 있다. 털린 블록의 가치 합에서 지나간 도로 구간의 비용 합을 뺀 값을 최대화하라. 같은 도로 구간을 두 번 지나면 지날 때마다 비용을 따로 낸다.

첫째 줄에 행의 수 $n$과 열의 수 $m$이 주어진다 ($1 \le n, m \le 200$). 다음 $n$개 줄에는 각각 $m$개의 정수가 주어지며, $i$번째 줄의 $j$번째 수가 $A_{ij}$이다 ($1 \le A_{ij} \le 100$). 다음 $n+1$개 줄에는 각각 $m$개의 정수가 주어지며, $i$번째 줄의 $j$번째 수가 $H_{ij}$이다 ($1 \le H_{ij} \le 1000$). 다음 $m+1$개 줄에는 각각 $n$개의 정수가 주어지며, $i$번째 줄의 $j$번째 수가 $V_{ij}$이다 ($1 \le V_{ij} \le 1000$).

가장 이익이 큰 계획의 이익을 출력한다. 답은 음수, 0, 양수 중 무엇이든 될 수 있다.