#joi2009yod. [joi2009yo_d]薄氷渡り

[joi2009yo_d]薄氷渡り

问题

在一个寒冷的冬日,JOI太郎决定去广场打碎薄冰玩耍。该广场是一个长方形区域,被分割成mmnn列,即m×nm \times n个小区域。其中,有一些区域有薄冰,有一些区域没有。JOI太郎根据以下规则移动并打碎薄冰:

  • 可以从任何有薄冰的区域开始打碎。
  • 可以向东、西、南、北四个方向之一移动到相邻的、尚未被打碎的有薄冰的区域。
  • 必须打碎移动后到达的区域的薄冰。

请编写一个程序来求出JOI太郎在打碎薄冰的同时最多可以移动到多少个区域。输入数据满足1m901 \leqq m \leqq 901n901 \leqq n \leqq 90。在给定的输入数据中,移动方式不会超过20万种。


输入

输入共有n+2n+2行。第1行为整数mm。第2行为整数nn。接下来的第3行到第n+2n+2行的每行包含mm个用空格分隔的整数,表示每个区域是否有薄冰。第i+2i+2行的第jj个值表示第(i,j)(i, j)个区域是否有薄冰。其中,1in1 \leqq i \leqq n1jm1 \leqq j \leqq m。如果第(i,j)(i, j)个区域有薄冰,则对应的值为11;如果没有薄冰,则对应的值为00

输出

输出可以移动到的区域的最大数量。


输入例子 1

3
3
1 1 0
1 0 1
1 1 0

输出例子 1

5

输入例子1的最大移动方式示例

2009-yo-t4-1.jpg


输入例子 2

5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1

输出例子 2

5

输入例子2的最大移动方式示例

2009-yo-t4-2.jpg

输入例子2的无法达到最大移动方式示例

2009-yo-t4-2-1.jpg

2009-yo-t4-2-2.jpg

2009-yo-t4-2-3.jpg

2009-yo-t4-2-4.jpg

2009-yo-t4-2-5.jpg