给你一个矩形蛋糕,表示为 r × c 网格。每个牢房要么有一个邪恶的草莓,要么是空的。例如,一个 3 × 4 的蛋糕可能如下所示:
蛋糕大师要吃蛋糕了!每次吃东西时,他都会选择不含任何邪恶草莓且至少含有一个以前没有吃过的蛋糕细胞的一行或一列,并吃掉那里的所有蛋糕细胞。他可能会决定吃多少次。
请输出cakeminator能吃掉的最大蛋糕单元数。
输入
第一行包含两个整数r和c(2≤r,c≤10),分别表示蛋糕的行数和列数。接下来的 r 行每行包含 c 个字符 - 第 i 行的第 j 个字符表示第 i 行和 j 列的单元格的内容,并且是以下之一:
- '.'字符表示没有邪恶草莓的蛋糕单元;
- “S”字符表示带有邪恶草莓的蛋糕单元。
输出
输出 cakeminator 可以吃掉的最大蛋糕单元数。
示例
输入 #1
3 4 S... .... ..S.
输出 #1
8
注意
对于第一个示例,吃掉最大数量的蛋糕单元的一种可能方法如下(执行 3 次吃)。