#CODEFORCESP7444. Bargaining Table(谈判桌)

    ID: 1179 远端评测题 2000ms 256MiB 尝试: 7 已通过: 4 难度: 10 上传者: 标签>brute forcedp*1500待翻译translated已润色

Bargaining Table(谈判桌)

题目翻译

鲍勃想在他的办公室里放一张新的谈判桌。为了做到这一点,他彻底测量了办公室房间,并画出了它的平面图:鲍勃的办公室是一个n×m米的长方形房间。房间的每一平方米要么被一些家具占据,要么空着。一张谈判桌是长方形的,在放之后,应该可以使它的边与办公室的墙平行。鲍勃不想改变或重新安排任何东西,这就是为什么所有将被桌子占据的方块最初都是空的。鲍勃希望新桌子能坐尽可能多的人,因此其周长应该是最大的。请帮助鲍勃找出他办公室的谈判桌的最大可能周长。

第一行包含两个隔开空间的数字nm(1≤nm≤25)--办公室的尺寸。然后是n行,每行有m个字符0或1。0代表办公房的可用的平方格(1平米)。1代表一个被占用的平方格(1平米)。保证房间里至少有一平方米是空闲的。

输出一个数字--鲍勃办公室的最大可能的谈判桌的周长。

Description

Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob's office room is a rectangular room n × m meters. Each square meter of the room is either occupied by some furniture, or free. A bargaining table is rectangular, and should be placed so, that its sides are parallel to the office walls. Bob doesn't want to change or rearrange anything, that's why all the squares that will be occupied by the table should be initially free. Bob wants the new table to sit as many people as possible, thus its perimeter should be maximal. Help Bob find out the maximum possible perimeter of a bargaining table for his office.

The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines with m characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It's guaranteed that at least one square meter in the room is free.

Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.

Input

The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines with m characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It's guaranteed that at least one square meter in the room is free.

Output

Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.

Samples

3 3
000
010
000
8
5 4
1100
0000
0000
0000
0000
16