Chocolate with Heart Marks

Time Limit : 5 sec, Memory Limit : 65536 KB

Problem F: Chocolate with Heart Marks

太郎君はチョコレートが大好きで, 学校から帰るとハートマークが描かれたお気に入りの板チョコを食べます, 最近の楽しみは, すべてのハートマークのブロックを最後まで残すように食べることです. 太郎君は, すべてのハートマークのブロックがつながったまま, できるだけ多くのハートマークのないブロックを食べようとします.

しかし太郎君はまだ幼く, 上記のように食べようとしても無駄なブロックが残ってしまいます. そこで太郎君は, すべてのハートマークのブロックをつながったまま残すときに食べられる最大のブロック数を求めるプログラムの作成をあなたに依頼しました.

太郎君は, すべてのハートマークのブロックがつながっている限り、どんな食べ方をしてもかまいません. ブロックのいずれか一辺が他のブロックに接していないと分かれていることになります.

Input

入力は複数のデータセットからなります. 各データセットは以下の形式で与えられます:

H W 
H × W 個の数字

H, W はそれぞれ板チョコの縦のサイズ, 横のサイズを示す整数です. H × W 個の数字はブロックの情報を表し, ハートマークのないブロックを表す '0', ハートマークのブロックを表す '1' から構成されます.

入力の終了は, H = W = 0 であるデータセットによって示されます. このケースに対して出力をしてはいけません.

1 ≤ H, W ≤ 12 であり、ハートマークのブロックの数は 6 個以下と仮定してかまいません.

Output

それぞれのデータセットに対して, 太郎君が食べられる最大のブロック数を出力してください.

Sample Input

4 4
1 0 0 0
0 0 1 0
0 1 0 0
1 0 0 1
1 1
1
2 3
1 0 0
0 0 1
0 0	 

Output for the Sample Input

7
0
2

Source: University of Aizu, ACM-ICPC Japan Domestic Contest 2009 Warm Up II , Aizu-Wakamatsu, Japan, 2009-06-28
Problem Setter:  Takayuki Shibata