题目描述

你是一名研究人员，一直在寻找可能成为未来食物的新型生物。最近，你发现了一种类似真菌的生物：它似乎很有营养，而且能够极其高效地把食物中的能量转化为自身质量。

你把一小团这种生物放入培养皿并为它准备了充足的食物。周末即将到来，你不想一直留在实验室观察它，但又担心它生长得太大，甚至侵蚀实验室的其他区域。

你用如下模型描述它的生长过程：

• 将无限平面划分为边长为 $1$ 的正方形网格；
• 某些格子当前被菌落占据；
• 每经过一个时间步，每个被占据的格子都会使它周围的八个相邻格子也被占据；
• 原本被占据的格子仍然保持被占据。

换言之，一个格子会向上下、左右以及四个对角方向同时扩张。

给定初始菌落和经过的时间步数 $k$，求 $k$ 个时间步之后被菌落占据的格子总数。

下图展示了样例 2 的菌落在经过 $0$、$1$、$2$ 个时间步后的状态。中间的图对应样例 2 的答案。

菌落生长示例

注意：输入只在一个有限网格中描述初始状态，但菌落可以并且很可能会生长到该网格之外。实际平面没有边界。

输入格式

第一行包含三个整数 $r,c,k$：

分别表示初始网格的行数、列数以及经过的时间步数。

接下来 $r$ 行，每行包含 $c$ 个字符。每个字符为：

• #：该格子最初被菌落占据；
• .：该格子最初未被菌落占据。

初始菌落不保证连通。

输出格式

输出一个整数，表示经过 $k$ 个时间步后，被菌落占据的格子总数。

样例 1

输入

5 5 3
.....
.###.
.#.#.
.###.
.....

输出

81

样例 2

输入

3 3 1
#..
.#.
..#

输出

19

样例 3

输入

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

输出

96

样例 4

输入

1 1 1000000
#

输出

4000004000001