쓰레기 치우기

방은 세로 N, 가로 M인 격자판으로 나타낸다. 왼쪽 위 칸의 좌표를 (0, 0), 오른쪽 아래 칸의 좌표를 (N - 1, M - 1)이라고 하자. 몇몇 칸에는 쓰레기가 놓여 있다.

로봇 한 대는 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착해야 한다. 이동할 때는 현재 칸에서 오른쪽 또는 아래쪽으로만 갈 수 있으며, 지나가는 칸의 쓰레기를 수거할 수 있다.

모든 쓰레기를 수거하려면 최소 몇 대의 로봇이 필요한지 구하라.

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100)

다음 N개의 줄에는 각 줄마다 M개의 수가 주어진다. 값이 0이면 해당 칸이 비어 있고, 1이면 해당 칸에 쓰레기가 있다는 뜻이다.

모든 쓰레기를 수거하는 데 필요한 로봇의 최소 대수를 출력한다.