問題文


白か黒の正方形のマスが列に敷き詰められています。
のとき列目は黒マスであり、 のとき列目は白マスです。
(白マスが少なくとも一つ存在します)
マスと合同な正方形からなる立方体があり、この立方体をマスにそってすべらないように転がします。
立方体は白マスの上のみを転がすことができます。黒マスの上に立方体が置かれることはありません。
立方体の面のうちつの面には赤いインクがついており、その面と密着した白マスを赤く塗ることができます。

はじめに、白マスをつ選び、自由な向きで立方体を選んだ白マスの上に置きます。
立方体を転がす回数に制限が無いとき、最大でいくつの白マスを赤く塗ることができますか。
ただし、立方体についてるインクは無制限であり、置いた立方体を持ち上げて再び別のマスに移動することはできないとします。

制約


  • または
  • 少なくとも1つは白マスが存在する。

入力






出力


赤く塗ることができる白マスの最大値を出力してください。

サンプル


入力1
2 4
.#.#
....
出力1
2

1行1列目の白マスに、インクの面が下になるように立方体を置きます。
(この時点でこの白マスが赤く塗られます。)
下右右上の順で立方体を転がすことで、再びインクの面が下にくるため、
1行3列目の白マスも赤く塗られます。
このとき、2つの白マスが赤く塗られ、これが最大です。


入力2
3 5
.....
#.##.
.....
出力2
6

入力3
2 6
..##..
#..#..
出力3
4

Submit


Go (1.14)