Many robots

Research robotics group is investigating collective behaviour of interacting groups of robots. The robots are positioned in a rectangular field divided into a grid of 1×1 meter cells. Non-moving robot is always inside some cell, never on a boundary. Each cells contains one non-negative integer. The movement of a robot in the field is divided into successive steps. In one step a robot can move either horizontally or vertically (in one row or in one column of cells) by some number of cells. The system is being tested and the additional movement rule is specified: A robot can move in one step from cell X to cell Y if and only if the distance between the centers of the cells X and Y measured in meters is equal to the sum of integers contained in X and Y.
We say that cell X is reachable for robot A if either A is currently standing in the cell X or A can reach X after some number of steps. During the transfer the robot can choose the direction (horizontal or vertical) of each step arbitrarily.

The initial task for the research group is to cover the field. Covering is a configuration in which for each cell there exists some robot for which this cell is a reachable one. For example, a trivial covering may consist of each cell containing one robot. Such covering is highly inefficient and also the research team might not have enough robots.

     

Image 1. Example of a 4×6 field with particular field values. It is enough to use 6 robots to cover this field. Each robot can be located in any of cells which are the same color as the robot. The colors in the example are used only as a visual aid, they are irrelevant in the experiment itself.

The task

Find the minimum number of robots needed to cover a given field.

Input

The first input line contains two integers M and N separated by space. The values indicate (in this order) the number of rows and columns in the field. Next, there are M lines of input, each represents one row of the field. The line contains N values separated by space and representing the particular cell values in the corresponding field row. The order of input values is the same as the order of values in the field.
Values of M and M do not exceed 500, also, each value in a field does not exceed 500.

Output

The output contains one text line with single integer representing the minimum number of robots needed to cover the given input field.

Example 1

Input
4 6
3 1 3 2 0 0
1 3 2 1 2 1
3 3 1 0 1 2
1 2 0 2 3 3
Output
6
Input configuration in Example 1 is depicted in Image 1 above.

Example 2

Input
9 9
1 4 1 4 1 4 1 4 1
4 1 4 1 4 1 4 1 4
1 4 1 4 1 4 1 4 1
4 1 4 1 4 1 4 1 4
1 4 1 4 1 4 1 4 1
4 1 4 1 4 1 4 1 4
1 4 1 4 1 4 1 4 1
4 1 4 1 4 1 4 1 4
1 4 1 4 1 4 1 4 1
Output
1

Example 3

Input
7 15
3 5 3 5 9 5 3 5 3 5 3 5 3 5 3
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
9 5 3 9 3 5 7 5 3 5 3 6 3 5 3
5 5 5 5 5 5 5 5 5 5 9 5 5 3 5
7 5 3 5 3 5 3 5 2 5 3 5 3 4 3
5 5 5 5 5 5 5 5 5 8 5 5 5 5 5
3 5 7 5 3 5 3 6 3 5 2 5 8 5 3
Output
67

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set