Collecting Mushrooms

Lim Li the Crab runs a mushroom plantation in her backyard. Her mushroom plantation can be modelled as a grid of R rows and C columns, and each cell can either be empty, contain a mushroom, or contain a sprinkler. For example, her plantation could look like this:

Figure 1: A mushroom farm with R = 5 and C = 5.

The distance between a sprinkler and a mushroom is the larger of their separations along the two axes. In other words, if the mushroom is at row Xm and column Ym and the sprinkler is at row Xs and column Ys, their distance is max(|Xs − Xm|, |Ys − Ym|). A sprinkler has a limited range, so it can water a mushroom only if the distance between them is at most D. For example, if D = 1, the areas the two sprinklers reach are:

Figure 2: The range of the sprinklers.

A mushroom can grow and be harvested only when enough sprinklers water it. Specifically, a mushroom is harvestable if at least K sprinklers water it. Count the number of harvestable mushrooms Lim Li can collect in her plantation.

The first line of input contains four integers: R, the number of rows, C, the number of columns, D, the maximum distance between a sprinkler and a mushroom it waters, and K, the minimum number of sprinklers needed for a mushroom to be harvestable.

The next R lines of input contain C characters each, forming a grid that represents the mushroom plantation. Each character represents the contents of one cell:

• '.' is an empty cell,
• 'M' is a cell containing a mushroom,
• 'S' is a cell containing a sprinkler.

Print one line with one integer, the maximum number of mushrooms Lim Li can harvest.

• 2 ≤ RC ≤ 500000,
• 1 ≤ D ≤ max(R, C),
• 1 ≤ K ≤ RC,
• there is at least one mushroom,
• there is at least one sprinkler.