Elevator Pitch

문제

You are in charge of ensuring all building designs meet accessibility requirements. As law dictates, every part of your building should be reachable for wheelchair users, which means elevators will have to be installed. You are given the blueprints of the company's current project and have to determine the minimum number of elevators required.

The floor plan is laid out on a square grid and the blueprints tell you the number of floors above any given square. You can place an elevator at any square, which stops at all floors of that square. A wheelchair user can move up and down between floors using the elevators and can freely move to any of the four adjacent squares on the same floor. Buildings do not connect diagonally.

The image below shows the second sample input. Designs can consist of multiple buildings; this one contains three buildings. The design requires two elevators: one for the pyramid-shaped building and one for the tall tower. The small building of height one does not require an elevator, since it only has a ground floor.

Figure E.1: A visualisation of the second sample input.

입력

• One line containing integers $hh$ and $ww$ ($1\le h,w\le 5001\backslash leq\; h,\; w\backslash leq\; 500$), the height and width of the grid.
• $hh$ lines of $ww$ integers each, where $x_{i,j}x\_\{i,j\}$ ($0\le x_{i,j}\le {10}^{9}0\backslash leq\; x\_\{i,j\}\; \backslash leq\; 10^9$), the $jj$th integer on the $ii$th line, denotes the number of floors at position $(i,j)(i,j)$ of the grid.

출력

Output the minimum number of elevators you need to build to be able to reach every part of the building(s) in the grid.

3 3
1 2 3
0 0 4
7 6 5

1

6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0

2

4 4
1 1 2 1
2 2 1 2
1 2 2 1
2 1 2 2

4