Under construction

Still being built. Things may change

Making a Shape

Interview

Time limit2sMemory limit512 MB

Summary
In a grid of 0s and 1s, find the largest connected group of 1s obtainable by flipping exactly one 0 cell to 1.
Level

Medium6 of 10

Topics
Graph, DFS, Union-find, Hash map
Solved
No attempts yet

Problem

We want to find shapes in an N×MN \times M grid. Each cell of the grid contains either 0 or 1. Two cells are adjacent if they share an edge.

When adjacent cells that contain 1 are connected, each connected component is called a shape. The size of a shape is the number of 1s it contains.

Find the maximum size of a shape that can be made by changing the number in one cell of the grid.

Input

The first line gives the dimensions of the grid, NN and MM. Each of the next NN lines gives the numbers in one row of the grid.

Output

Print the maximum size of a shape that can be made by changing one number.

Constraints

  • 2≤N,M≤1,0002 \le N, M \le 1{,}000
  • There is at least one 0 and at least one 1.

Examples3

  1. Example 1

    Input
    3 3
0 1 1
0 0 1
0 1 0
    Expected output
    5

  2. Example 2

    Input
    5 4
1 1 0 0
1 0 1 0
1 0 1 0
0 1 1 0
1 0 0 1
    Expected output
    10

  3. Example 3

    Input
    3 4
0 1 0 1
0 0 0 1
1 1 0 1
    Expected output
    6