Lizard Escape

On a grid of r rows and c columns, there are stone pillars of various heights. The pillar at row \(i\) and column \(j\) has a height of \(h_{i,j}\). Some pillars have lizards on them. Your task is to help as many lizards as possible escape from the grid to the outside.

The grid is arranged such that the distance between adjacent pillars (in any row or column) is \(1\). A lizard can jump to any other pillar whose Euclidean distance (i.e. plane distance) is at most \(d\). Note that the distance between the centers of the pillars \((i,j)\) and \((u,v)\) is \(\sqrt{(i-u)^2+(j-v)^2}\).

The pillars are unstable. Every time a lizard jumps from a pillar, the height of that pillar decreases by \(1\). If a pillar had a height of \(1\), then right after a lizard jumps off it, the pillar disappears and no other lizard can use it.

Furthermore, at any moment, no two lizards can be on the same pillar. (However, a pillar can be used repeatedly in sequence as long as it is not destroyed.)

A lizard is considered to have escaped if, from the pillar it currently occupies, it can make a jump to a position outside the grid. In particular, if the pillar is close enough to the boundary (i.e. if it is on the border of the grid), the lizard can jump out directly.

Determine the maximum number of lizards that can escape.

Note: When a lizard jumps, if it is departing from a pillar that initially had a lizard, that jump consumes 1 unit of the pillar's height; hence, such a pillar can be used for at most \(h_{i,j} - 1\) future jumps. For a pillar without an initially standing lizard, it can serve as a stepping stone for up to \(h_{i,j}\) jumps. You may assume that each pillar has a height of at least \(1\).

inputFormat

The first line contains three integers \(r\), \(c\) and \(d\) (the number of rows, columns, and the maximum jump distance), separated by spaces.

The next \(r\) lines each contain \(c\) integers representing the heights \(h_{i,j}\) of the pillars.

The next \(r\) lines each contain a string of length \(c\). Each character is either 'L' (indicating that a lizard starts at that pillar) or '.' (no lizard on that pillar).

outputFormat

Output a single integer: the maximum number of lizards that can escape from the grid.

sample

3 3 1
2 2 2
2 2 2
2 2 2
...
.L.
...

1