You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

任何人都会对某事感到害怕。有些怕黑，有些怕高，还有些惧怕 Vinnie Jones……

题目描述

Mirko 最害怕的是寻找合适的土地来种植草莓。他的土地可以用一个 $N \times M$ 的矩阵来表示。土地中有些田地适合种植草莓，而有些不适合，因为那里杂草丛生。

Mirko 正在寻找一块合适矩形。当土地中有一块矩形区域包含的所有田地均适合种植草莓，则该矩形被称为合适矩形。

Mirko 还对所有田地的潜力值感兴趣。一块田地的潜力值定义为包含该田地的合适矩形的个数。

求 Mirko 所有田地的潜力值之和。

输入格式

第一行输入正整数 $N,M$，表示土地的规模。

接下来的 $N$ 行，每行输入 $M$ 个字符。其中 . 表示该块田地适合种植草莓，而 # 表示不适合。

输出格式

输出 Mirko 所有田地的潜力值之和。

2 3
.#.
..#

8

3 3
...
...
...

100

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

40

提示

样例 1 解释

下列矩阵代表各个田地的潜力值。所有田地潜力值总和为 $8$。

数据规模与约定

对于 $20\%$ 的数据，$1 \le N,M \le 10$。

对于另外 $30\%$ 的数据，$1 \le N,M \le 300$。

对于 $100\%$ 的数据，$1 \le N,M \le 2000$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2018-2019 CONTEST #1 T4 Strah。