인덕이와 보드게임

시간 제한1초메모리 제한1024 MB

요약

격자판의 각 칸에 값과 색이 주어질 때, (1,1)에서 (N,M)까지 오른쪽과 아래쪽으로만 이동하며 검은 칸에서는 부호가 반전될 때 공에 적힐 수 있는 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

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

<설명서>

보드게임을 처음 시작하면 $N \times M$ 격자판 모양 보드의 각 칸에 임의의 정수가 하나씩 써지고, 모든 칸이 흰색 또는 검은색으로 칠해지게 됩니다. 단, $1$ 행 $1$ 열은 항상 흰색으로 칠해집니다.

이후 보드의 $1$ 행 $1$ 열에 공이 하나 소환되며 이 칸에 적혀있는 수가 공에 기록됩니다. 이 공은 안뇽이의 특수한 마법이 걸려 있어 대각선 방향으로 이동할 수 없으며, 한 번에 변으로 인접한 다른 한 칸으로만 이동할 수 있습니다.

공이 다른 칸으로 이동을 마치면 해당 칸에 적혀 있는 수가 공에 더해지게 됩니다. 이 때, 검은색 칸으로 이동한 경우 수가 더해진 뒤 공에 적힌 수의 부호가 반전됩니다. 흰색 칸으로 이동한 경우에는 부호 반전이 일어나지 않습니다.

이제 규칙을 준수하며 공을 $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}$

예제2

예제 1
입력
```
2 2
100 20
-30 70
0 0
0 1
```
예상 출력
```
-140
```

예제 2

입력

2 5
2 -5 1 -3 5
3 -8 -3 5 8
0 1 0 0 0
1 1 0 1 1

예상 출력