28083번 - 마왕의 성

문제

세계 정복의 야망을 품은 마왕은 자신의 국가를 만들기로 했다! 하지만 국가를 만들기 전, 영토를 정하거나 성을 세우는 등 해야 할 일이 많다.

영토가 될 수 있는 부지는 \(N \times M\)크기의 직사각형 모양이며, 부지는 \(1 \times 1\)단위 크기의 땅으로 나뉘어져 있다. 마왕은 하나 이상의 땅을 골라 자신의 영토로 선포하고, 그 중 하나의 땅에 마왕의 성을 세울 것이다. 각 땅에는 "땅의 높이"와 "얻을 수 있는 세금" 두 가지 수치가 정해져 있다. 다음 그림은 예제 2의 각 땅에서 얻을 수 있는 세금과 높이를 각각 나타낸 것이다.

마왕은 국민과의 소통을 중시하므로, 영토에 속하는 모든 땅은 상하좌우로 인접한 영토를 따라 이동해 마왕의 성에 도달할 수 있어야 한다. 또한 자신이 세상에서 가장 높은 사람이 되어야 한다는 확고한 철학이 있으므로, 마왕의 성을 세울 땅은 나머지 모든 영토의 높이보다 높거나 같아야 한다.

마왕이 얻을 수 있는 세금의 양은 영토에 포함된 각각의 땅에서 얻을 수 있는 세금의 합과 같다. 마왕은 \(N \times M\)개의 땅 각각에 성을 세울 때 최대 얼마 만큼의 세금을 얻을 수 있는지 알고 싶다. 하지만 마왕은 프로그래밍을 할 줄 모르기 때문에, 마왕에게 사로잡힌 여러분이 이 문제를 해결할 프로그램을 대신 작성해 보자.

입력

첫째 줄에 영토가 될 수 있는 부지의 크기 $N,ドル $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 ($i,ドル $j$)에 위치한 땅의 높이 $h_{ij}$가 $M$개씩 공백으로 구분되어 주어진다.

$N$ + 1번째 줄부터 $N$개의 줄에 걸쳐 ($i,ドル $j$)에 위치한 땅을 마왕의 영토로 만들 때 얻을 수 있는 세금 $c_{ij}$가 $M$개씩 공백으로 구분되어 주어진다.

출력

$N$개의 줄에 걸쳐 각 위치에 마왕의 성이 있는 경우 영토를 적당히 선포하여 걷을 수 있는 세금의 합의 최댓값을 $M$개씩 공백으로 구분하여 출력한다.

제한

• 1 ≤ $N,ドル $M$ ≤ 1,000
• 1 ≤ $h_{ij},ドル $c_{ij}$ ≤ 10⁹

힌트