Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2922
Bombs

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A building has N*M rooms ( N rows and M columns 1<=N,M<=1000 ) . And there are bombs in some of these rooms. Each bomb has a power K which means when the bomb explodes, the K (K<1000) rooms on its left will all be destroyed, and the bombs in these rooms will explode automatically. The bomb has a special property, when a bomb exploded, the rooms above it will be destroyed and the bombs in these rooms will also explode automatically.

For example:

            A E I Q
            B F J R
            C G L S
            D H P T

When the bomb in room L explodes, and the power of that bomb is 1.Then the bombs in G and J and I will explode.

Now you task is to count at least how many bombs should be exploded by bomb expert so that all the bombs will explode.

Input

There are multiple test cases. There are two integers N and M on the first line of each case. In the next N lines followed, each line has M non-negative integers: K1 K2 ... KM, in which Ki is the power of the ith bomb. Ki=0 means there is no bomb in that room.

Process to the end of file.

Output

For each case, output the answer in a line, at least how many bombs should be exploded by bomb expert.

Sample Input


2 2
0 1
1 0
2 2
1 1
1 1
3 3
1 0 2
0 0 0
1 0 2
4 4
3 0 1 0
0 0 0 0
0 0 0 0
0 3 0 1

Sample Output


2
1
1
4


Author: CHEN, Ximing
Source: ZOJ Monthly, February 2008
Submit    Status