Isolamento

Recentemente, a cidade de Bytelandia, que esta passando por uma grande onda de crimes, decidiu isolar uma certa parte da cidade com uma cerca, para impedir o acesso de criminosos. A cidade pode ser representada por uma grade de $n$ linhas e $m$ colunas, com $n \times m$ quarteirões. As linhas são numeradas de $0$ a $n-1$, sendo o extremo norte da cidade a linha $0$ e  o extremo sul a linha $n - 1$, e as colunas numeradas de forma semelhante, com o extremo oeste sendo a coluna $0$ e o extremo leste sendo a coluna $m - 1$. O $j$-ésimo quarteirão na $i$-ésima linha vale para a cidade $A_{ij}$. Antes da primeira linha, entre qualquer par de linhas consecutivas, e após a última linha, existem ruas na direção leste oeste, de mão dupla. As $n+ 1$ ruas leste-oeste são numeradas de $0$ a $n$ de forma semelhante as colunas e linhas. Esse padrão de ruas também existe entre as colunas, porém ruas norte-sul, também de mão dupla, também numeradas de $0$ a $m$. Cada rua pode por sua vez, ser dividida em segmentos. As ruas leste-oeste têm $m$ segmentos cada, e as norte-sul $n$,que delimitam os quarteirões, e têm intersecções. Chamaremos a intersecção da $i$-ésima rua leste-oeste com a $j$-ésima rua norte-sul de $T(i,j)$. Além disso, como Bytelandia é uma cidade grande e cara, existem preços para atravessar os segmentos de rua. Atravessar o $j$-ésimo segmento da $i$-ésima rua leste-oeste custa $H_{ij}$. De modo semelhante, atravessar o $j$-ésimo segmento da $i$-ésima rua norte-sul custa $V_{ij}$.

Para isolar partes da cidade, eles colocarão cercas saindo de $T(0,0)$ até $T(n,m)$, indo apenas para leste e para sul, e então voltarão indo apenas para o norte e oeste. Eles terão que pagar os valores para atravesar, e só receberão os valores dos quarteirões completamente cercados, ou seja, que, se partindo deles, não é possível sair da grade de ruas sem passar por uma cerca. A figura ilustra um possível plano de isolamento do caso de teste.

Ajude a prefeitura de Bytelândia, achando qual é o máximo que pode ser ganho, ou seja, a máxima diferença entre os valores recebidos e os valores pagos.

Entrada

A primeira linha de entrada contém dois inteiros, $n$ e $m$.

As próximas $n$ linhas contém $m$ inteiros cada, os valores dos quarteirões, o $j$-ésimo número da $i$-ésima linha sendo $A_{ij}$.

As próximas $n + 1$ linhas contém  $m$ inteiros cada, os valores dos segmentos leste oeste, o $j$-ésimo número da $i$-ésima linha sendo o valor $H_{ij}$.

Então, as próximas $m + 1$ linhas contém $n$ inteiros cada, o $j$-ésimo número da $i$-ésima linha sendo o valor $V_{ij}$.

Saída

A saída deve conter um único inteiro, o maior valor que pode ser ganho. Note que isso pode ser um valor negativo, positivo, ou até zero.

Restrições

• $1 \leq n, m \leq 200$
• $1 \leq A_{ij} \leq 100$
• $1 \leq H_{ij}, V_{ij} \leq 1000$

Exemplos

Entrada	Saida
2 3 6 7 3 12 10 7 4 13 5 2 5 5 12 12 6 3 7 6 4 6 2 9 4	-28

Para submeter sua solução, use esse link, no problema F.