Khu dân cư

Bản đồ thành phố \(X\) có dạng lưới ô vuông \(M\) hàng \(N\) cột, các hàng được đánh số từ \(1\) tới \(M\), các cột được đánh số từ \(1\) tới \(N\). Mỗi một ô vuông trên bản đồ có thể là khu đất trống hoặc một khu dân cư hoặc một 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 so với nó không quá \(D\), nghĩa là nếu siêu thị nằm ở ô \((x, y)\) thì nó có thể phục vụ được tất cả các khu dân cư nằm trong hình vuông có ô trái trên là \((x - D, y - D)\), ô phải dưới là \((x + D, y + D)\) (hình vuông gồm các ô \((u, v)\) với \(|u - x| \le D\) và \(|v - y| \le D\), phần nằm ngoài bản đồ bị bỏ qua).

Một khu dân cư gọi là chất lượng cao'' nếu được ít nhất $K$ siêu thị có thể phục vụ nó. Cho biết bản đồ của thành phố $X$, hãy đếm số lượng khu dân cưchất lượng cao''.

Input

Dữ liệu vào:

• Dòng đầu chứa bốn số nguyên \(M, N, D\) và \(K\) (\(1 \le D \le \max(M, N)\); \(1 \le K \le M \times N\));

• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) ký tự, mỗi ký tự biểu diễn một ô vuông bản đồ. Mỗi ký tự sẽ thuộc ba loại sau:

  • `.' biểu diễn một khu đất trống;

• `P' biểu diễn một khu dân cư;

• `M' biểu diễn một siêu thị.
  Dữ liệu đảm bảo tồn tại ít nhất một khu dân cư và ít nhất một siêu thị.

Ràng buộc:

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thoả mãn: \(M = 1\); \(N, D \le 10^3\);

• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: \(M = 1\); \(N \le 10^5\);

• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thoả mãn: \(2 \le M, N \le 1000\); số khu dân cư, số siêu thị không vượt quá \(1000\);

• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thoả mãn: \(2 \le M, N \le 1000\).

Output

In ra

Ghi ra một số duy nhất là số khu dân cư ``chất lượng cao''.

Example

Input:

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

Output:

1

Note

Bản đồ có ba khu dân cư và hai siêu thị (ô \((3,4)\) và ô \((4,2)\)), với \(D = 1\) và \(K = 2\):

• Khu dân cư ở ô \((1,1)\) không được siêu thị nào phục vụ;

• Khu dân cư ở ô \((2,5)\) được một siêu thị có thể phục vụ (siêu thị ở ô \((3,4)\));

• Khu dân cư ở ô \((3,3)\) được hai siêu thị có thể phục vụ (cả hai siêu thị).
  Vậy có một khu dân cư ``chất lượng cao''.