33926번 - 인덕이와 보드게임

문제

인덕이는 보드게임을 정말 좋아한다! 최근에는 안뇽이가 만들어준 보드게임에 푹 빠져서 헤어나오지 못하는 중이다. 같이 이 보드게임의 설명서를 읽어보자.

<설명서>

1. 보드게임을 처음 시작하면 $N \times M$ 격자판 모양 보드의 각 칸에 임의의 정수가 하나씩 써지고, 모든 칸이 흰색 또는 검은색으로 칠해지게 됩니다. 단, 1ドル$행 1ドル$열은 항상 흰색으로 칠해집니다.
2. 이후 보드의 1ドル$행 1ドル$열에 공이 하나 소환되며 이 칸에 적혀있는 수가 공에 기록됩니다. 이 공은 안뇽이의 특수한 마법이 걸려 있어 대각선 방향으로 이동할 수 없으며, 한 번에 변으로 인접한 다른 한 칸으로만 이동할 수 있습니다.
3. 공이 다른 칸으로 이동을 마치면 해당 칸에 적혀 있는 수가 공에 더해지게 됩니다. 이 때, 검은색 칸으로 이동한 경우 수가 더해진 뒤 공에 적힌 수의 부호가 반전됩니다. 흰색 칸으로 이동한 경우에는 부호 반전이 일어나지 않습니다.
4. 이제 규칙을 준수하며 공을 $N$행 $M$열까지 최단거리로 이동시키면 됩니다. 도착했을 때 공에 적혀 있는 수가 가능한 최댓값이라면 공이 맛있는 너겟으로 바뀌게 됩니다!

인덕이는 수도 없이 이 보드게임을 했지만 단 한 번도 맛있는 너겟을 따내지 못했다. 인덕이가 보드게임을 성공적으로 끝마치고 맛있는 너겟을 먹을 수 있게, 여러분들이 인덕이 대신 가능한 최댓값을 구해주자. 인덕이한테 가능한 최댓값만 알려주면, 인덕이가 공을 굴리는 방법을 찾아내는 데 큰 도움이 될 것이다.

입력

첫 번째 줄에 보드의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $N$은 보드의 행의 수, $M$은 보드의 열의 수를 나타낸다.

이어서 $N$개의 줄에 $i$행 $j$열에 적혀 있는 정수 $B_{ij}$가 공백으로 구분되어 주어진다.

이어서 $N$개의 줄에 보드의 $i$행 $j$열의 색상 정보가 공백으로 구분되어 주어진다. 0ドル$이면 흰색, 1ドル$이면 검은색으로 칠해져 있음을 의미한다. 1ドル$행 1ドル$열은 항상 흰색으로 칠해져 있음이 보장된다.

출력

공이 $(N, M)$까지 최단거리로 이동하여 도착했을 때, 공에 적힐 수 있는 수의 최댓값을 출력한다.

제한

• 2ドル \le N \le 1,000円$
• 2ドル \le M \le 1,000円$
• $-10^{9} \le B_{ij} \le 10^{9}$

힌트