Noise Level

The Berland's의 수도는 크기가 n × m인 직사각형 형태의 구역들로 이루어져 있다. 모든 구역은 세 가지 유형으로 나뉜다:

• 일반 구역(문자 '.'으로 표시) — 이러한 구역은 소음을 발생시키지 않지만 소음 전파를 막지는 않는다;
• 소음원(대문자 라틴 문자 'A'부터 'Z'까지 중 하나로 표시) — 이러한 구역은 소음원이며 소음 전파를 막지는 않는다;
• 고밀도 건축-up 구역(문자 '*'로 표시) — 이러한 구역은 방음 처리되어 소음이 내부로 침투하지 않으며, 그 자체가 소음 전파를 막는 장애물이다.

문자 'A'로 표시된 구역은 q 단위의 소음을 발생시킨다. 문자 'B'로 표시된 구역은 2·q 단위의 소음을 발생시킨다. 이런 식으로 계속되어, 문자 'Z'로 표시된 구역은 up 26·q 단위의 소음을 발생시킨다. 도시에는 각 문자로 표시된 구역이 임의의 개수만큼 있을 수 있다.

소음원에서 소음이 전파될 때, 한 구역에서 변을 공유하는 구역으로 이동할 때마다 소음 수준은 절반이 된다(홀수를 절반으로 나누어야 하는 경우에는 내림한다). 소음은 구역들의 사슬을 따라 퍼진다. 예를 들어 어떤 구역이 소음원에서 거리 2에 있다면, 그 구역에 도달하는 소음의 값은 4로 나누어진다. 따라서 소음원에서 해당 구역으로 오는 소음 수준은 둘 사이의 최단 경로 길이만으로 결정된다. 고밀도 건축-up 구역은 장애물이며, 소음은 그 내부로 침투하지 않는다.

오른쪽 표의 각 칸에 있는 값은 q = 100일 때 해당 구역의 총소음 수준을 나타내며, 각 합의 첫 번째 항은 구역 'A'에서 오는 소음이고 두 번째 항은 구역 'B'에서 오는 소음이다.

한 구역의 소음 수준은 모든 소음원에서 오는 소음의 합으로 정의한다. Berland 수도 주민의 삶의 질을 평가하기 위해, 소음 수준이 허용 수준 p를 초과하는 구역의 수를 구해야 한다.

첫 번째 줄에는 네 정수 n, m, q, p (1 ≤ n, m ≤ 250, 1 ≤ q, p ≤ 106)이 주어진다. 이는 Berland 수도의 크기, 구역 'A'가 발생시키는 소음 단위의 수, 허용 소음 수준을 나타낸다.

이어지는 n개의 각 줄에는 m개의 문자가 주어진다. 이는 위의 문제 설명에서 기술한 형식으로 표현된 수도 구역의 설명이다. Berland의 수도에는 어떤 유형의 구역도 없을 수 있다.

소음 수준이 허용 수준 p를 초과하는 구역의 수를 출력한다.

첫 번째 예제의 그림은 문제 설명의 본문에 있다.