</p>

$N$행 $M$열 크기의 격자판이 있고, 이 격자판의 $(N,M)$ 위치에는 맛있는 치킨이 놓여 있다. 곰곰이는 $(1,1)$ 에서 출발하여 치킨을 향해 이동하려 한다. 곰곰이는 상하좌우 방향으로 자유롭게 이동할 수 있지만, 장애물이 있는 칸으로 이동하거나 격자판 바깥으로 나갈 수는 없다.

곰곰이의 헬스 트레이너인 총총이는 곰곰이가 치킨으로 이동하는 것을 막기로 했다. 총총이는 현재 장애물이 없는 칸에 장애물을 새로 놓아 곰곰이의 이동을 방해할 수 있다. 만약 격자판에 벌써 장애물이 놓여 있는 칸이 있다면, 총총이는 새로 장애물을 놓는 횟수를 절약할 수 있을지도 모른다.

격자판의 상태가 주어졌을 때, 총총이가 곰곰이의 이동을 막기 위해 추가로 놓아야 할 장애물의 최소 개수를 출력하라. $(1, 1)$ 과 $(N, M)$ 에는 장애물을 놓을 수 없다.

입력 형식

첫째 줄에 정수 $N, M$이 공백을 사이에 두고 주어진다. ($1 \le N, M \le 2\ 000$, $3 \le N \times M$)</p>

둘째 줄부터 $N$개의 줄에 걸쳐 격자판의 상태가 주어진다. $0$이면 지나갈 수 있는 칸, $1$이면 장애물이 있어 지나갈 수 없는 칸을 뜻한다.

$(1,1)$ 과 $(N,M)$ 에는 장애물이 없음이 보장된다.

출력 형식

곰곰이의 이동을 막기 위해 총총이가 추가로 놓아야 할 장애물의 최소 개수를 출력하라.

예제 입력 1

4 4
0 0 0 1
0 0 0 0
0 0 1 0
0 1 0 0

예제 출력 1

1

예제 입력 2

3 3
0 1 1
1 1 1
1 1 0

예제 출력 2

0

예제 입력 3

9 10
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 1 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력 3

2