Mức tiếng ồn

Thành phố có dạng lưới hình chữ nhật gồm $n\times m$ ô. Mỗi ô thuộc một trong ba loại:

• Ô thường (ký hiệu .): không phát ra tiếng ồn và không cản trở tiếng ồn lan truyền.
• Nguồn ồn (ký hiệu bằng một chữ cái in hoa từ A đến Z): là nguồn phát tiếng ồn, đồng thời cũng không cản trở tiếng ồn lan truyền.
• Ô cách âm (ký hiệu *): tiếng ồn không thể đi vào, và những ô này là vật cản đối với sự lan truyền của tiếng ồn.

Một ô mang chữ A phát ra $q$ đơn vị tiếng ồn, ô mang chữ B phát ra $2q$ đơn vị, và cứ như vậy, ô mang chữ Z phát ra $26q$ đơn vị.

Khi lan truyền từ nguồn, mỗi lần đi từ một ô sang ô kề cạnh (chung một cạnh), mức tiếng ồn bị chia đôi và làm tròn xuống (lấy phần nguyên của phép chia cho $2$). Tiếng ồn lan theo chuỗi các ô kề nhau, không đi qua ô cách âm. Do đó mức tiếng ồn mà một nguồn truyền tới một ô chỉ phụ thuộc vào độ dài đường đi ngắn nhất giữa nguồn và ô đó (tính theo số bước di chuyển giữa các ô kề cạnh, không đi qua ô *). Cụ thể, nếu đường đi ngắn nhất từ nguồn có giá trị phát $V$ đến một ô là $d$ bước, thì mức tiếng ồn từ nguồn đó tại ô là $\lfloor V/2^d\rfloor$ (áp dụng liên tiếp phép chia đôi làm tròn xuống). Nếu không có đường đi từ nguồn đến ô thì nguồn đó không đóng góp gì cho ô.

Mức tiếng ồn tại một ô bằng tổng mức tiếng ồn từ tất cả các nguồn truyền tới ô đó (bản thân ô nguồn cũng nhận đóng góp từ chính nó và từ các nguồn khác).

Hãy đếm số ô có mức tiếng ồn vượt quá ngưỡng cho phép $p$ (tức là lớn hơn $p$ một cách chặt).

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $q$, $p$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả các ô của thành phố theo định dạng đã nêu.

Dữ liệu ra

In ra một số nguyên: số ô có mức tiếng ồn vượt quá $p$.

Ràng buộc

• $1\le n,m\le 250$
• $1\le q,p\le {10}^6$
• Có thể không có ô nào thuộc một loại bất kỳ.

Ví dụ