薩格勒布市政府決定建造一座新的停車場。他們將利用一塊矩形土地，這塊土地可以想像成一個 $N$ 列 $M$ 行的矩陣。為了吸引顧客並增加收入，市長決定在預先選定的土地位置上設置噴泉、水井、飲水台及其他類型的噴泉。其餘的空間則規劃為車輛行駛區域，並將被改建為以下兩種用途之一：

• 停車位，或
• 車輛自由行駛區域。

車輛在停車場內的移動方式為：每一步可以移動到四個方向（北、南、東或西）中的相鄰格子。停車場的設計必須確保在任何時刻，從每個停車位都能到達位於左上角（第一列與第一行的交點）的停車場出入口，也就是說，停在停車位上的車輛不會阻擋其他車輛的出口。換句話說，每一輛停放的車輛都必須能夠在不移動其他已停放車輛的情況下離開停車場。

請協助市長計算給定土地配置下，最多能設置的停車位數量。

說明：位於第一列與第一行的格子是停車場的出入口，不作為停車位使用，且該位置將始終保持暢通。

輸入格式

第一行包含自然數 $N$ 和 $M$ ($1 \le N \le 6, 1 \le M \le 100$)，分別代表土地的列數與行數。 接下來的 $N$ 行，每行包含 $M$ 個字元，描述土地的配置：

• 字元 'x' 代表將要建造噴泉的格子，
• 其餘格子以字元 '.' 表示，將被改建為停車場區域。

輸出格式

在唯一的一行中，輸出所求的最大停車位數量。

子任務

範例

輸入 1

3 3
...
.x.
...

輸出 1

2

輸入 2

3 3
...
..x
...

輸出 2

4

輸入 3

3 6
.x..x.
..x.x.
......

輸出 3

3

輸入 4

4 5
....x
....x
..x..
.x..x

輸出 4

7

說明 4

第四個範例的一種可能停車位配置：

.PPPx
....x
.Px.P
PxP.x