#B4263. Maximizing Cultivable Land

    ID: 11920 Type: Default 1000ms 256MiB

Maximizing Cultivable Land

Maximizing Cultivable Land

You are given a grid representing a piece of land with n rows and m columns. Each cell is either free from debris or contains debris. A cell that is free (without debris) can be cultivated if and only if all of its existing four directionally adjacent neighbors (up, down, left, right) are also free from debris.

You are allowed to remove debris from at most one cell (i.e. convert a debris cell into a free cell). Determine the maximum number of cells that can be cultivated under the optimal debris removal (or no removal) strategy.

Note: For cells on the border, only the neighbors that exist within the grid are considered.

Input Format: The grid is provided in the following format. See the input description below for details.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of rows and columns of the grid.

Each of the next n lines contains m space-separated integers. Each integer is either 0 or 1, where 0 indicates that there is no debris (i.e. the cell is initially free) and 1 indicates that the cell contains debris.

outputFormat

Output a single integer which is the maximum number of cultivable cells after removing debris from at most one cell.

sample

3 3
0 1 0
1 0 1
0 1 0
1