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.