버섯 수확

게 Crab인 Lim Li는 뒷마당에서 버섯 농장을 운영한다. 그녀의 버섯 농장은 R개의 행과 C개의 열로 이루어진 격자로 나타낼 수 있고, 각 칸은 비어 있거나, 버섯이 있거나, 스프링클러가 있다. 예를 들어 그녀의 버섯 농장은 다음과 같을 수 있다.

그림 1: R = 5, C = 5인 버섯 농장.

스프링클러와 버섯 사이의 거리는 두 축에서의 간격 중 큰 값으로 정의한다. 즉, 버섯이 Xm번째 행 Ym번째 열에 있고 스프링클러가 Xs번째 행 Ys번째 열에 있으면 두 칸 사이의 거리는 max(|Xs − Xm|, |Ys − Ym|)이다. 스프링클러는 사거리가 제한되어 있어 거리가 D 이하인 버섯만 물을 줄 수 있다. 예를 들어 D = 1이면 두 스프링클러가 물을 줄 수 있는 영역은 다음과 같다.

그림 2: 스프링클러의 사거리를 나타낸 그림.

버섯은 충분한 스프링클러가 물을 줘야 자라고 수확할 수 있다. 구체적으로, 버섯에 물을 주는 스프링클러가 K개 이상이면 그 버섯을 수확할 수 있다. Lim Li가 농장에서 수확할 수 있는 버섯의 개수를 세라.

입력의 첫 줄에는 네 정수 R, C, D, K가 주어진다. R은 행의 수, C는 열의 수, D는 스프링클러와 물을 받는 버섯 사이의 최대 거리, K는 버섯을 수확하기 위해 필요한 최소 스프링클러의 수이다.

다음 R개의 줄에는 각각 C개의 문자가 주어지며, 버섯 농장을 나타내는 격자를 이룬다. 각 문자는 해당 칸의 내용을 다음과 같이 나타낸다.

• '.'는 빈 칸,
• 'M'은 버섯이 있는 칸,
• 'S'는 스프링클러가 있는 칸.

Lim Li가 수확할 수 있는 버섯의 최대 개수를 한 줄에 하나의 정수로 출력한다.

• 2 ≤ RC ≤ 500000,
• 1 ≤ D ≤ max(R, C),
• 1 ≤ K ≤ RC,
• 버섯이 적어도 하나 있다,
• 스프링클러가 적어도 하나 있다.