The Demon King's Castle

A Demon King with ambitions of conquering the world has decided to found his own nation! But before he can form a nation, he has many things to do, such as choosing territory and building a castle.

The site that can become territory is an $N \times M$ rectangle divided into $1 \times 1$ plots of land. The Demon King selects one or more plots and declares them his territory, then builds his castle on one of those plots. Each plot has two values: its "height" and the "tax it yields." The figure below shows the tax and height of each plot in Sample 2.

The Demon King values communication with his people, so every plot in the territory must be able to reach the castle by moving through adjacent territory plots up, down, left, or right. He also firmly believes he must be the highest person in the world, so the plot with the castle must be at least as high as every other plot in the territory.

The total tax the Demon King collects equals the sum of the taxes of all plots in the territory. He wants to know the maximum tax he can collect for each of the $N \times M$ plots as the castle location. He cannot program, so you, captured by the Demon King, must write a program to solve this.

The first line contains $N$ and $M$, separated by a space.

The next $N$ lines each contain $M$ heights $h_{ij}$ of the plots, separated by spaces.

The following $N$ lines each contain $M$ taxes $c_{ij}$ of the plots, separated by spaces.

Print $N$ lines, each with $M$ integers separated by spaces. The $j$-th number on the $i$-th line is the maximum total tax when the castle is built on plot $(i, j)$.

$1 \le N, M \le 1,000$

$1 \le h_{ij}, c_{ij} \le 10^9$