Trash Cleanup

Time limit2sMemory limit128 MB

Summary
Given a grid with trash cells, find the minimum number of top-left-to-bottom-right monotone paths needed to cover every trash cell.
Level

Medium7 of 10

Topics
Dynamic programming, Sorting, Greedy, Math
Solved
No attempts yet

Problem

A room is represented as a grid with N rows and M columns. The upper-left cell is (0, 0), and the lower-right cell is (N - 1, M - 1). Some cells contain trash.

Each robot starts at the upper-left cell and must finish at the lower-right cell. From its current cell, it may move only to the right or downward, and it can collect trash from every cell it visits.

Find the minimum number of robots needed to collect all trash.

Input

The first line contains N and M separated by a space. (1 <= N, M <= 100)

Each of the next N lines contains M integers. A value of 0 means the cell is empty, and a value of 1 means the cell contains trash.

Output

Print the minimum number of robots needed to collect all trash.

Examples1

  1. Example 1

    Input
    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
    Expected output
    3