#joi2017yoc. [joi2017yo_c]休憩スペース (Refreshment Area)

[joi2017yo_c]休憩スペース (Refreshment Area)

问题

将世界级的编程竞赛在日本举办,目前正在进行会场的布置。该会场沿南北方向划分为 NN 个格子,沿东西方向划分为 MM 个格子,并且在一些格子上放置了竞技用的设备。

为了让选手在比赛中休息,决定在会场内设置一个休息区,可以放置小吃和饮料等。休息区必须是由南北方向或者东西方向连续的 DD 个格子组成的。但是,不能在放置设备的格子上设置休息区。

请编写一个程序来计算在会场内设置休息区的方法有多少种。


输入

输入由 1+N1 + N 行组成。

第一行包含 33 个整数 N,M,DN, M, D (1N1001 \leqq N \leqq 1001M1001 \leqq M \leqq 1002D1002 \leqq D \leqq 100),表示会场沿南北方向划分为 NN 个格子,沿东西方向划分为 MM 个格子,并且休息区由南北方向或者东西方向连续的 DD 个格子组成。

接下来的 NN 行中,每行包含 MM 个字符,表示会场的信息。其中,第 ii 行的第 jj 个字符 (1iN1 \leqq i \leqq N1jM1 \leqq j \leqq M) 是一个 # 或者 .,分别表示该格子上放置了设备或者没有放置设备。

输出

在会场内设置休息区的方法总数,以一行输出。


输入示例 1

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

输出示例 1

12

在示例 1 中,如下图所示,共有 1212 种设置休息区的方法。

2017-yo-t3-fig01.png


输入示例 2

4 7 5
.#.....
.....##
.......
#......

输出示例 2

7