A swamp has a rectangular shape, with nl rows and nc columns. It is made of cells with the side of one unit length. A part of these cells represent land, other cells water. The land is coded with 0, and the water with 1. We want to obtain a path from the North shore to the South shore, without passing through water. A water cell can be transformed into land by parachuting on it a pontoon having the size of the cell. Because parachuting is dangerous, we want a minimum number of parachutes. We can move only one cell on the same row, the same column or the same diagonal.

The input file LAC.IN has the following structure:

• on the first line there are nl and nc separated by a space, representing the number of rows ad the number of columns of the swamp;
• on each of the next nl lines there are nc binary values separated by spaces, representing the configuration of the zone (0 for land, 1 for water)

The output file LAC.OUT will have the following structure:

• the number min, which represents the minimum number of pontoons

• 1£ nl£ 100
• 1£ nc£ 100

Observation:

Example: