Hide

Problem F
Hiding Treasure

The “No Name Pirates” crew have just concluded a …lucrative expedition and now they’re looking to safely store the spoils of their labours. However, as a crew they’ve come up with several rules to ensure their treasure will be kept well hidden:

  1. Only one chest can be hidden on each island,

  2. Chests must be square and can hold up to 10 coins per unit area,

  3. The chest must be completely buried in sand, and

  4. Chests cannot neighbour the ocean.

The “No Name Pirates” have found a map and want to determine how much treasure they can hide in the region it depicts. Can you help them determine how many coins they can hide?

Additional Notes:

  1. Two areas are considered neighbours if and only if they are adjacent in one of the cardinal directions (North, East, South, West).

  2. The region beyond the map is assumed to be ocean.

  3. Any two neighbouring sand or mountain areas (can be one of each) are a part of the same island.

Example: The first sample case gives the following map which contains a single island where the largest possible chest is $2 \times 2$ (indicated by the x’s). Therefore, the maximum amount of coins we can store is $10\cdot (2^2)=40$.

\includegraphics[scale=0.75]{sample1}
Figure 1: In this case there were two locations where we could have put the $2\times 2$ chest.

Input

The first line of the input will consist of two integers $n$ and $m$ $(1\leq n,m\leq 2000)$. The following $n$ lines will consist of $m$ characters from the following: “0” representing ocean, “1” representing sand, or “2” representing mountains. This is the map of the region the pirates are considering (the entire map is surrounded by ocean).

Output

Output a single integer $t$ the most treasure (in coins) the crew can hide in the region while following their rules.

Sample Input 1 Sample Output 1
5 5
01110
01112
01112
02112
02222
40
Sample Input 2 Sample Output 2
5 5
00000
01000
00111
00111
00111
10
Sample Input 3 Sample Output 3
7 8
01210000
12111000
21111000
11111000
00000111
00002111
00000111
50

Please log in to submit a solution to this problem

Log in