곰곰이의 식단 관리 2

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

곰곰이의 헬스 트레이너인 총총이는 곰곰이가 치킨으로 가지 못하도록 막기로 했다. 총총이는 현재 장애물이 없는 칸에 장애물을 새로 놓아 곰곰이의 이동을 방해할 수 있다. 격자판에 이미 장애물이 놓인 칸이 있다면, 총총이는 새로 놓는 장애물의 수를 줄일 수도 있다.

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

첫째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 2\ 000$, $3 \le N \times M$)

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

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

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