5006 - 2022信息与未来T2:沙滩面积

通过次数

3

提交次数

9

Time Limit : 1 秒
Memory Limit : 128 MB

我们获得了一个陆地和水域情况的卫星照片,照片可以看成是一个n行m列的矩形,矩形中的每个格子要么是陆地(用半角点.表示),要么是水域(用#表示)。 虽然卫星照片可以看清楚地辨别出陆地和水域,但陆地的具体类型却不明确,现在我们了解到,对于一块是水域的方格,它向上、下、左、右四个方向k布之内可达的陆地格子,均会形成沙滩。例如,下图展示了k=2的情况,蓝色的格子代表水域,标为黄色的陆地格子是沙滩! 你的任务是根据卫星照片计算出属于沙滩的格子数量,注意:卫星照片只拍摄了包含水域的部分,水域附近的沙滩可能出现在卫星照片的边界之外,你可以假设卫星照片之外不存在任何水域

Input

输入的第一行是空格分隔的三个整数n,m,k,代表拍摄的卫星照片共有n行m列,以及形成沙滩的范围k. 接下来n行,每行一个字符串。字符串的长度恰好是m,代表卫星照片的一行,其中 井号#表示一片水域; 半角点号.表示一片陆地

Output

输出一行一个整数,代表沙滩格子的数量

Examples

Input

2 4 2
##.#
...#

Output

26

Input

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

Output

103

Hint

对于40%的数据,满足n=m=1 对于100%的数据,满足1<=n,m<=100;1<=k<=10