该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

广场被鸭鸭们攻占了，现在要开货车去将他们都回收。

Description

现有一个n×m的网格广场，广场上有些地方是空地，有些地方是鸭子。
现在你有很多1×2和2×1的货车，你需要用将尽量少的货车放入广场使得广场上无法放置任何另外一辆货车，同时你不可以让货车相撞或者压到鸭鸭。
求最优方案下货车的最少个数。

Format

Input

第一行两个正整数n和m，即广场大小，其中n<=70,m<=7.
接下来一个n×m大小的字符串矩阵，描述网格广场。
其中字符'.'表示此处为空地'*'表示此处为鸭鸭，详见样例。

Output

一行一个正整数，表示最少需要的货车个数。

Sample 1

Input

5 5
.*..*
*....
..**.
**.*.
.**..

Output

4

Limitation

1s, 128Mb for each test case.

Source

lyhlyhlyh