시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 4 4 40.000%

문제

방은 세로 N, 가로 M (1 <= N, M <= 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레기를 로봇을 사용해서 수거하려고 하는데, 로봇은 왼쪽 위에서 출발해 오른쪽 아래로 도착한다. 즉, 로봇은 현재 위치에서 오른쪽, 혹은 아래쪽으로밖에 이동할 수 없다.

이 때, 모든 쓰레기를 수거하기 위해서 필요한 최소 로봇의 수를 출력하는 프로그램을 작성하시오.

입력

첫 행에는 N, M이 공백으로 구분되어 주어진다.

다음 N 행에 걸쳐 M 개의 수가 주어진다. 이 값이 0이면 해당하는 위치가 비어 있다는 뜻이고, 1이면 해당하는 위치에 쓰레기가 있음을 뜻한다.

출력

필요한 최소 로봇의 수를 출력한다.

예제 입력

5 6
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 0 1 0
0 1 1 0 0 0
0 0 0 0 0 0

예제 출력

3

힌트

출처