测试数据来自 system/1877

描述

小岛玩的塔防游戏是一个经典的电脑游戏, 尤其受到学生的欢迎.
在游戏中有一张N*M的地图,地图的每个格子内可能是如下三种元素之一:

1) '*' : 代表空白区域
2) 'O' : 代表一个目标物
3) 'X' : 代表一个障碍物

例如, 下面就是一张塔防地图:

**O**
*OXO*
*****
**O**

假设现在有一些具有相同射程R的塔. 定义地图中两格之间的距离为:

dist(G1,G2) = |R1-R2| + |C1-C2|

其中, R1, C1 分别是G1格所在的行号和列号, R2, C2 分别是G2格所在的行号和列号(最上方的行号为0, 最左方列号为0)
每个塔可以攻击所有与其距离小于等于R的目标物, 并且对目标物造成1点的伤害.
每一个空白格子最多放置一个塔, 已经放有障碍物的格子或者放有目标物的格子里不能再放塔.

现在给定一张地图, 塔的射程以及塔的个数, 你能够计算出这张地图上所有目标物能够受到的最大伤害总和吗?

格式

输入格式

第一行包含4个整数, N, M, T, R. 其中N和M分别表示地图的行数和列数, T表示塔的个数, R代表每一个塔可以攻击目标的最大距离.
接下来N行,每行含有一个长度为M的字符串, 表示这张地图.

输出格式

一个整数, 表示可以得到的最大伤害

样例1

样例输入1

3 3 2 1
*O*
OXO
***

样例输出1

4 

限制

对于40%的数据: 1<=N,M,R<=100.
对于100%的数据: 1<=N,M<=1000, 1<=T<=1000, 1<=R<=10^8, 所有答案均保证在64位带符号长整型范围内.

每一个测试点的时间限制为1秒.