一只老鼠遇到了一个漂亮的大蛋糕,决定在上面散步,并在途中吃掉蛋糕顶部的浆果。蛋糕呈长方形,整齐地分成正方形;有些方块里有浆果,有些则没有。
不过,老鼠有点着急,所以一旦她从西北角(输入数据中的左上角单元格)进入蛋糕,她只会向东(右侧)或向南(向下)移动,直到到达东南角(右下角单元格)。她会吃掉她经过的方格中的所有浆果,但不会吃掉其他方格中的浆果。
老鼠尝试选择自己的路径,以便最大限度地消耗浆果数量。然而,她的匆忙和饥饿可能会影响她的判断,导致她做出次优的决定……
输入
输入的第一行包含两个整数 $$$H$$$ 和 $$$W$$$ ($$$1 \le H, W \le 5$$$),用空格分隔,即蛋糕的高度和宽度。
接下来的 $$$H$$$ 行每行包含一个由 $$$W$$$ 字符组成的字符串,代表该行中蛋糕的方块:“.”代表一个空的方块,“*”代表一个有浆果的方块。
输出
输出老鼠按照她的策略将吃掉的浆果数量。
示例
输入 #1
4 3 *.. .*. ..* ...
输出 #1
3
输入 #2
4 4 .*.. *... ...* ..*.
输出 #2
2
输入 #3
3 4 ..** *... ....
输出 #3
1
输入#4
5 5 ..*.. ..... **... **... **...
输出#4
1