你的朋友 Ellie 拥有一家名为 Grid City Parcel Courier (GCPC) 的本地包裹递送公司，该公司在 Grid City 运营。Grid City 是一个城镇，所有的房屋都排列在矩形的街道网格上。每座房屋都位于两条街道的交叉口，一条街道呈南北走向（垂直），另一条街道呈东西走向（水平）。网格中有 $w$ 条垂直街道和 $h$ 条水平街道，形成了 $h \times w$ 的房屋网格。

为了扩大业务，Ellie 也想开始提供包裹揽收服务。然而，Grid City 的市长最近决定，为了缓解交通拥堵，白天所有的街道都将改为单行道。在此期间，Grid City 的街道只能分别从北向南或从西向东通行。

图 G.1：第一个样例输入中单行道网格的可视化。

Ellie 已经在城市最西北角的交叉口租用了一个大型车库，她的司机将从那里出发开始他们的揽收行程。她请求你帮助她计算出，为了在白天揽收所有包裹并将它们带到位于城市最东南角的物流中心，她需要雇佣多少名司机。

输入格式

输入包含： 一行，包含两个整数 $h$ 和 $w$ ($1 \le h, w \le 2\,000$)，表示网格的高度和宽度。 $h$ 行，每行包含 $w$ 个字符，字符为 C（表示需要揽收包裹的客户房屋）或 _（表示无需揽收的房屋）。

输出格式

输出在所有街道均为单行道的情况下，揽收所有包裹所需的最少司机人数。

样例

输入 1

4 4
__C_
C_C_
_C_C
_CCC

输出 1

2

输入 2

4 6
CC____
_CCC__
___C_C
C__CCC

输出 2

2

输入 3

3 5
CC__C
_C_CC
CCCCC

输出 3

3