Maximum Damage

The orcs and the elves have been at war for a long time, and the fighting has reached a decisive moment. The elves have located every orc camp and marked it on a map of the battlefield. To simplify their planning, the elves lay a coordinate grid over the battlefield and treat each unit square as a single point with integer coordinates, so every orc camp is described by a pair of integers (its x- and y-coordinates).

The elves want to build a limited number of Elf stations to strike the camps. Each station deals 1 unit of damage to every orc camp within distance $R$ of it, so the total damage a single station inflicts equals the number of orc camps within distance $R$.

Because the elves' cavalry rides along horizontal and vertical trails laid out in a grid, distance is measured with the Manhattan metric rather than straight-line distance. For two points $P_1$ and $P_2$,

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

Some parts of the battlefield are too rugged to build on; the elves call such cells obstacles. The elves want to decide where to build a given number $T$ of Elf stations so as to inflict the maximum possible total damage on the orc camps.

The battlefield is a rectangular map in which every cell is one of three characters:

• * — a blank cell, where an Elf station may be built;
• O — an orc camp;
• X — an obstacle, where no Elf station may be built.

An Elf station may be built only on a blank (*) cell, and each blank cell can hold at most one station. A station's damage is the number of orc camps whose Manhattan distance to it is at most $R$. You place at most $T$ stations (fewer if there are fewer than $T$ blank cells) so as to maximize the sum of their damage. A legal battlefield map looks like this:

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

The first line contains the number of test cases (fewer than 15). The test cases follow one after another.

Each test case begins with a line of four integers $N$, $M$, $T$, $R$: $N$ and $M$ are the size of the battlefield along the y- and x-axes (the number of rows and columns), $T$ is the number of Elf stations you may place, and $R$ is each station's attack radius. The next $N$ lines each contain a string of $M$ characters describing one row of the map.

For each test case, print a single line in the form

Maximum damage = X

where X is the maximum total damage that can be inflicted on the orc camps.

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