Khu dân cư

Bản đồ thành phố \(X\) có dạng lưới ô vuông gồm \(M\) hàng và \(N\) cột (đánh số hàng từ \(1\) đến \(M\), cột từ \(1\) đến \(N\)).
Mỗi ô vuông là một trong ba loại:

• '.': khu đất trống,
• 'P': khu dân cư,
• 'M': siêu thị.

Mỗi siêu thị chỉ có thể phục vụ các khu dân cư có khoảng cách không vượt quá \(D\) theo nghĩa sau:
nếu siêu thị nằm tại ô \((x,y)\) thì nó phục vụ được mọi ô nằm trong hình vuông có góc trên trái \((x-D, y-D)\) và góc phải dưới \((x+D, y+D)\)
(chỉ tính các ô nằm trong lưới).

Một khu dân cư được gọi là chất lượng cao nếu được ít nhất \(K\) siêu thị có thể phục vụ.
Hãy đếm số khu dân cư chất lượng cao.

\InputFile
Dòng đầu tiên chứa bốn số nguyên \(M, N, D, K\) \((1 \le D \le \max(M,N),\, 1 \le K \le M \cdot N)\).

\(M\) dòng tiếp theo, mỗi dòng gồm \(N\) ký tự mô tả bản đồ.

Dữ liệu đảm bảo tồn tại ít nhất một ô 'P' và ít nhất một ô 'M'.

\OutputFile
In ra một số nguyên duy nhất là số khu dân cư chất lượng cao.

Example

5 5 1 2
P....
....P
..PM.
.M...
.....

1