시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

문제

The orcs and the elves have been fighting for a long time, and the war between them has come to a critical juncture. The elves have detected all the locations for the orc camps, and marked them on a map of the battle ground. To simplify their calculations, elves have laid out a coordinate grid over the battleground, and they treat each unit square as a point (with integer coordinates). So the location of each orc camp is given by a pair of integers, denoting the x- and y-coordinates. The elves would like to build a limited number of Elf stations to attack those camps. Each of the stations is capable of inflicting 1 unit of damage to each of the orc camps within a distance R (from the station). Thus the total damage that a single Elf station can inflict is given by the number of orc camps within distance R from it.

However, “distance” between two points on the battle ground is not the standard straight-line distance between them. This is because the horse trails that the elves would use to launch the attacks are laid horizontally and vertically, in a grid-like manner. So, given two locations P1 and P2 on the battle ground , the distance between them is:

D(P1, P2) = |P1.x - P2.x| + |P1.y - P2.y|

where P1.x and P1.y denote the x- and y-coordinates of P1. Given the above discretization assumption, all the coordinates are positive integers.

The elves have also noticed that parts of the battle ground are too rugged to build an Elf station on – they call such locations “obstacles”. With all the information in hand, the elves would like to identify the ideal locations to build a given number T of Elf stations, so as to inflict the maximum possible damage on the orc camps.

The battle ground is described by a rectangular map where each location is annotated using one of three: ’*’, ’O’ and ’X’. An asterisk ’*’ represents a blank space (a location at which an Elf station can be built), a letter ’O’ represents an orc camp and a letter ’X’ means an obstacle (a location that none of the Elf stations can be built on). A legal battleground map is shown below.

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

입력

The first line in the test data file contains the number of test cases (< 15). Each of the test cases is continued one after another.

For each test case, the first line contains 4 integers: N, M, T, R. The first two, N and M, indicate the size of the battleground along the y and x axes, respectively. T represents the number of Elf stations that can be placed on the map. R represents the maximum attack distance for each Elf station.

Following N lines, each of which contains a string of M characters, represents the map of the battleground.

출력

For each test case, you are to output one line containing only one integer, representing the maximum harm that can be inflicted upon the orc camps.

제한

• 1 ≤ N,M ≤ 1000
• 1 ≤ T ≤ 106
• 1 ≤ R ≤ 108

출력 형식

정확한 출력 형식은 제출에서 언어를 Java로 설정하면 확인할 수 있다.

예제 입력 1

2
3 3 2 1
*O*
OXO
***
4 5 3 2
**O**
*OXO*
*****
**O**


예제 출력 1

Maximum damage = 4
Maximum damage = 8