题目描述

公司的办公室可以表示为一个 $H$ 行 $W$ 列的网格。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i,j)$。

每个格子的状态由字符 $S_{i,j}$ 表示：如果 $S_{i,j}$ 是 #，表示该格子放置了一张桌子；如果 $S_{i,j}$ 是 .，表示该格子是地板。题目保证网格中至少存在两个地板格子。

你需要选择两个不同的地板格子，并在每个格子上各放置一台加湿器。

放置加湿器后，一个格子 $(i,j)$ 能够被加湿，当且仅当它与至少一台加湿器所在的格子 $(i',j')$ 之间的曼哈顿距离不超过 $D$。格子 $(i,j)$ 和 $(i',j')$ 之间的曼哈顿距离定义为 $|i-i'| + |j-j'|$。注意，放置了加湿器的地板格子本身也总是会被加湿。

请问，最多能有多少个地板格子被加湿？

输入格式

第一行包含三个整数 $H, W$ 和 $D$ —— 分别表示网格的行数、列数以及加湿器的有效曼哈顿距离。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串。其中第 $i$ 行的第 $j$ 个字符 $S_{i,j}$ 表示格子 $(i,j)$ 的状态。

输出格式

输出一行，一个整数，表示最多能够被加湿的地板格子的数量。

样例输入 1

2 5 1
.###.
.#.##

样例输出 1

3

样例输入 2

5 5 2
.#.#.
.....
.#.#.
#.#.#
.....

样例输出 2

15

样例输入 3

4 4 2
....
.##.
.##.
....

样例输出 3

10

说明

样例解释

在第一个样例中，如果在 $(1,1)$ 和 $(1,5)$ 处放置加湿器：

• 由 $(1,1)$ 处的加湿器，$(1,1)$ 和 $(2,1)$ 这两个地板格子会被加湿。
• 由 $(1,5)$ 处的加湿器，$(1,5)$ 这个地板格子会被加湿。

总共有 $3$ 个地板格子被加湿。没有任何一种放置方案能够加湿 $4$ 个或更多的地板格子，因此答案为 $3$。

在第二个样例中，如果在 $(2,4)$ 和 $(5,3)$ 处放置加湿器，将会有 $15$ 个地板格子被加湿。

数据范围

对于所有测试点，保证：

• $1 \le H, W \le 10$。
• $H \times W \ge 2$。
• $0 \le D \le H+W-2$。
• 保证 $S_{i,j}$ 均为 # 或 .（$1 \le i \le H$，$1 \le j \le W$）。
• 保证至少存在两个状态为 . 的格子。
• 保证所有的输入数值均为整数。