최대 피해

오크와 엘프는 오랫동안 전쟁을 벌여 왔고, 이제 전투는 결정적인 국면에 이르렀다. 엘프들은 모든 오크 진영의 위치를 파악해 전장 지도에 표시했다. 계산을 단순화하기 위해 엘프들은 전장에 좌표 격자를 씌우고 각 단위 칸을 정수 좌표를 갖는 하나의 점으로 취급한다. 따라서 각 오크 진영의 위치는 두 정수(x좌표와 y좌표)의 쌍으로 주어진다.

엘프들은 진영을 공격하기 위해 제한된 수의 엘프 기지를 세우려 한다. 각 기지는 자신으로부터 거리 $R$ 이내에 있는 모든 오크 진영에 1의 피해를 입힌다. 따라서 한 기지가 입히는 전체 피해는 거리 $R$ 이내에 있는 오크 진영의 수와 같다.

엘프 기병은 격자 모양으로 놓인 가로·세로 길만 따라 이동하므로, 두 지점 사이의 거리는 직선 거리가 아니라 맨해튼 거리로 잰다. 두 점 $P_1$, $P_2$에 대해

$$D(P_1, P_2) = |P_1.x - P_2.x| + |P_1.y - P_2.y|$$

이다. 전장의 일부는 지형이 험해 기지를 세울 수 없는데, 엘프들은 이런 칸을 장애물이라 부른다. 엘프들은 주어진 수 $T$개의 기지를 어디에 세울지 정해 오크 진영에 입히는 전체 피해를 최대로 만들고자 한다.

전장은 직사각형 지도로 주어지며, 각 칸은 다음 세 문자 중 하나이다.

• * — 빈 칸으로, 엘프 기지를 세울 수 있다.
• O — 오크 진영.
• X — 장애물로, 엘프 기지를 세울 수 없다.

엘프 기지는 빈 칸(*)에만 세울 수 있으며, 한 빈 칸에는 최대 한 개의 기지만 세울 수 있다. 한 기지의 피해는 그 칸까지의 맨해튼 거리가 $R$ 이하인 오크 진영의 수이다. 빈 칸이 $T$개보다 적으면 그 수만큼만 세울 수 있다. 최대 $T$개의 기지를 세워 피해의 합을 최대로 하라. 올바른 전장 지도의 예는 다음과 같다.

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

첫째 줄에 테스트 케이스의 수가 주어진다(15 미만). 테스트 케이스는 차례대로 이어진다.

각 테스트 케이스의 첫째 줄에는 네 정수 $N$, $M$, $T$, $R$가 주어진다. $N$과 $M$은 각각 전장의 y축(행)과 x축(열) 크기이고, $T$는 세울 수 있는 엘프 기지의 수, $R$는 각 기지의 공격 반경이다. 이어지는 $N$개의 줄에는 각각 $M$개의 문자로 이루어진 문자열이 주어져 지도의 한 행을 나타낸다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Maximum damage = X

여기서 X는 오크 진영에 입힐 수 있는 최대 전체 피해이다.

• $1 \le N, M \le 1000$
• $1 \le T \le 10^6$
• $1 \le R \le 10^8$