일요일 밤, 내일 학교에 가는 것이 괴로워지기 시작했다.</p>

학교에 가지 않을 핑계를 만들기 위해서, 집에서 학교로 가는 길에 벽을 잘 세워 집에서 학교로 가는 길을 모두 막기로 결정하였다.

학교와 집이 있는 동네는 N*M의 칸으로 이루어져있다. 집은 (1, 1)에 위치하고, 학교는 (N, M)에 위치한다.

각각의 칸은 3가지 종류로 나뉜다.

• 이미 벽이 존재하는 칸 (-2로 나타낼 것이다.)
• 벽이 존재하지 않으며, 벽을 세울 수 없는 칸 (-1로 나타낼 것이다.)
• 벽이 존재하지 않으며, 비용을 지불하면 벽을 세울 수 있는 칸 (비용이 적혀있을 것이다.)

우리는 3번 종류의 칸에 적절히 벽을 세워서 집에서 학교로 가는 길을 막을 것이다. 단, 돈을 절약하기 위해서 비용을 최소로 하고 싶다. 다만 어떻게 벽을 지어도 막을 수 없는 경우가 있을 수 있는데, 이러한 경우도 판단해서 알려주어야 한다.

집에서 학교로 이동할 때는 상하좌우로만 이동할 수 있으며(대각선 방향으로는 이동할 수 없다), 주어진 격자판(N*M) 밖으로 이동할 수 없다. 또한, 집과 학교가 위치한 칸은 벽을 세울 수 없는 칸임이 보장된다.

입력 형식

첫 번째 줄에는 지도의 행의 수 N, 열의 수 M이 공백을 사이로 주어진다. (2 ≤ N, M ≤ 300) 다음 N 줄에는 각각 M 개 정수가 주어진다. -2는 벽이 있음을 의미하고, -1은 벽을 세울 수 없는 장소를 의미하며, 0 이상의 정수는 벽을 세울 수 있는 장소이며, 정수는 벽을 세우는 비용을 의미한다. 비용 값은 10억을 넘지 않는 정수이다. i 번째 줄의 j 번째 문자는 (i, j)의 정보를 나타낸다.</p>

집과 학교가 위치한 칸((1, 1)와 (N,M))에는 -1가 들어옴이 보장된다.

출력 형식

첫째 줄에 학교를 갈 수 없게 만드는 최소 비용을 출력한다. 단, 학교를 갈 수 없게 길을 막을 수 없다면, -1을 출력한다

예제 입력 1

3 3
-1 1 -2
1 1 1
1 1 -1

예제 출력 1

2

예제 입력 2

5 5
-1 -1 5 -2 -2
-1 5 7 8 4
-2 5 -2 9 1
-2 8 11 2 -1
-2 9 1 -1 -1

예제 출력 2

4

예제 입력 3

5 5
-1 -1 -1 -2 -2
-1 5 -1 -1 -1
-2 -2 -2 9 -1
-2 8 11 2 -1
-2 9 1 -1 -1

예제 출력 3

-1

힌트

예제1 설명</p>

..#
..
..

으로 막으면 가능하다,