월요병

일요일 밤, 내일 학교에 갈 생각을 하니 괴로워지기 시작했다.

학교에 가지 않을 핑계를 만들려고, 집에서 학교로 가는 길에 벽을 세워 모든 길을 막기로 했다.

동네는 $N \times M$ 칸의 격자로 이루어져 있다. 집은 $(1, 1)$에, 학교는 $(N, M)$에 있다.

각 칸은 다음 세 종류 중 하나이다.

• 이미 벽이 있는 칸 ($-2$로 나타낸다)
• 벽이 없고, 벽을 세울 수도 없는 칸 ($-1$로 나타낸다)
• 벽이 없고, 비용을 내면 벽을 세울 수 있는 칸 (그 비용으로 나타낸다)

세 번째 종류의 칸에 적절히 벽을 세워 집에서 학교로 가는 길을 모두 막으려 한다. 돈을 아끼기 위해 드는 비용은 최소로 하고 싶다. 어떻게 벽을 세워도 길을 막을 수 없는 경우도 있으니, 그런 경우도 판단해야 한다.

집에서 학교로 이동할 때는 상하좌우로만 움직일 수 있고(대각선으로는 움직일 수 없다), 격자 밖으로 나갈 수 없다. 벽이 있는 칸으로는 들어갈 수 없다. 집과 학교가 있는 칸은 벽을 세울 수 없는 칸임이 보장된다.

첫째 줄에 지도의 행의 수 $N$과 열의 수 $M$이 공백으로 구분되어 주어진다. ($2 \le N, M \le 300$)

다음 $N$개의 줄에는 각각 $M$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 칸 $(i, j)$의 정보이다. $-2$는 이미 벽이 있는 칸, $-1$은 벽을 세울 수 없는 칸이다. $0$ 이상의 정수는 벽을 세울 수 있는 칸이며, 그 값이 벽을 세우는 비용이다. 비용은 $10^9$ 이하의 정수이다.

집과 학교가 있는 칸 $(1, 1)$과 $(N, M)$에는 항상 $-1$이 주어진다.

첫째 줄에 학교에 갈 수 없게 만드는 최소 비용을 출력한다. 어떻게 해도 길을 막을 수 없다면 $-1$을 출력한다.

첫 번째 예제는 다음과 같이 막으면 된다. #은 원래 있던 벽, *는 새로 세운 벽, .은 벽이 없는 칸이다.

..#
.*.
.*.

새로 세운 벽 두 개의 비용은 각각 $1$이므로 총비용은 $2$이다.