Counting Good Mushrooms

Lim Li created a mushroom plantation in her garden, which can be represented as an \(R \times C\) grid. Each cell of the grid is either empty, contains a mushroom, or contains a sprinkler.

The distance between a mushroom at \( (X_m, Y_m) \) and a sprinkler at \( (X_s, Y_s) \) is defined as \[ d = \max(|X_m-X_s|,\,|Y_m-Y_s|), \] which is the maximum of the absolute differences of their row and column indices. A sprinkler can water any mushroom within a distance of \(D\) (i.e. \(d \le D\)).

A mushroom is considered a good mushroom if it is watered by at least \(K\) sprinklers. Your task is to count the number of good mushrooms in the grid.

Input Format: The input starts with a line containing four integers \(R\), \(C\), \(D\), and \(K\). The following \(R\) lines each contain a string of length \(C\) representing the grid. In the grid, the character M represents a mushroom, S represents a sprinkler, and . represents an empty cell.

Output Format: Output a single integer, the number of good mushrooms in the plantation.

inputFormat

The first line contains four space-separated integers \(R\) \(C\) \(D\) \(K\) where:

• \(R\) and \(C\) denote the number of rows and columns of the grid, respectively.
• \(D\) is the maximum distance a sprinkler can water a mushroom.
• \(K\) is the minimum number of sprinklers required for a mushroom to be considered good.

The next \(R\) lines each contain a string of exactly \(C\) characters consisting only of the characters M, S, and ..

outputFormat

Output a single integer: the number of good mushrooms in the grid.

sample

3 3 1 1
M.S
...
.SM

1