#2738 재재새와 삼겹살

2 s   128 MB  

Description

재재새는 삼겹살을 좋아한다.

 

재재새는 냉동 삼겹살 보다는 생 삼겹살을 더 좋아한다.

 

재재새는 욕심이 아주 아주 많다.

 

재재새는 현재 수원(1,1)에 있다.

 

재재새는 활발하기 때문에 이쪽 저쪽으로 움직인다.

 

재재새는 다이어트를 하는 중이다.

 

따라서, 최소한으로 고기를 먹으려고 한다.

 

수원에서 시작해서, 서울(r, c)에 도착할 때 까지, 고기를 최소한으로 먹어주면 된다.

 

재재새를 도와주자.

 

이동은 (위(W), 아래(S), 왼쪽(A), 오른쪽(D)) 4방향으로 가능하다.

 

한번 지났던 곳을 다시 지날 수 있으며, 다시 지날 때는 쿨하게 고기를 먹지 않는다.

 

재재새를 도와주자

Input

재재새가 활동할 영역의 크기가 주어진다.

R, C $1 \leq R, C \leq 1000$

 

R x C 만큼 그 지역에서 재재새가 먹을 수 있는 삼겹살의 양이 주어진다.

(각 지역에서 삼겹살의 양은 0 ~ 1000이다)

Output

다이어트를 하는 재재새를 위해 재재새가 수원부터 서울까지 갈때까지

재재새가 먹을 수 있는 최소한의 삼겹살의 양을 출력한다.

Sample Input

Sample Output

3 3
0 1 0
0 0 1
1 0 1
1

HINT

(1, 1)은 좌측 상단 (R, C)는 우측 하단

Source

wowoto9772