对于 Mirko 来说，没有比找到一卷新的胶带更让他高兴的事了。今天他特别高兴，因为他还找到了 Slavko 的降临节日历（Advent calendar）。

降临节日历可以表示为一个 $n$ 行 $m$ 列的网格。每个格子都包含一个小窗口，每个窗口后面都有一块巧克力。Slavko 已经打开了其中的一些窗口，而其他的窗口仍然关闭着。

Mirko 决定用他的胶带把所有关闭的窗口都封上。胶带是无限长的，宽度正好为一个网格单元格。Mirko 可以撕下一段胶带，用它来封住一连串在水平或垂直方向上相邻的关闭窗口。他不想在任何一个窗口上贴超过一段胶带，因为他还想和 Slavko 保持朋友关系（即胶带不能重叠）。

他想知道，最少需要多少段胶带才能把所有关闭的窗口都封上。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1000$，$1 \le m \le 10$），表示降临节日历的尺寸。

接下来的 $n$ 行，每行包含 $m$ 个字符 . 和 #，表示降临节日历的状态。字符 . 表示一个打开的窗口，字符 # 表示一个关闭的窗口。

输出格式

输出封住所有关闭的窗口所需的最少胶带段数。

子任务

样例

输入样例 1

2 3
#.#
###

输出样例 1

3

输入样例 2

4 3
.#.
###
.##
.#.

输出样例 2

3

输入样例 3

4 4
####
#.#.
#.##
####

输出样例 3

5

说明

对于样例 1： 一种可行的方案是：用一段胶带贴住第一列（共两个窗口），一段胶带贴住第三列（共两个窗口），再用一段胶带贴住第二行第二列的窗口。