萨格勒布市政府决定建造一个新的停车场。他们将利用一块矩形土地，我们可以将其想象为一个有 $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

说明

第四个样例的说明：一种可能的停车位布局：

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