The Berland's capital has the form of a rectangle with sizes _n_ × _m_ quarters. All quarters are divided into three types:
* regular (labeled with the character '_._') — such quarters do not produce the noise but are not obstacles to the propagation of the noise;
* sources of noise (labeled with an uppercase Latin letter from '_A_' to '_Z_') — such quarters are noise sources and are not obstacles to the propagation of the noise;
* heavily built-up (labeled with the character '_*_') — such quarters are soundproofed, the noise does not penetrate into them and they themselves are obstacles to the propagation of noise.
A quarter labeled with letter '_A_' produces _q_ units of noise. A quarter labeled with letter '_B_' produces 2·_q_ units of noise. And so on, up to a quarter labeled with letter '_Z_', which produces 26·_q_ units of noise. There can be any number of quarters labeled with each letter in the city.
When propagating from the source of the noise, the noise level is halved when moving from one quarter to a quarter that shares a side with it (when an odd number is to be halved, it's rounded down). The noise spreads along the chain. For example, if some quarter is located at a distance 2 from the noise source, then the value of noise which will reach the quarter is divided by 4. So the noise level that comes from the source to the quarter is determined solely by the length of the shortest path between them. Heavily built-up quarters are obstacles, the noise does not penetrate into them.
<center> The values in the cells of the table on the right show the total noise level in the respective quarters for _q_ = 100, the first term in each sum is the noise from the quarter '_A_', the second — the noise from the quarter '_B_'.</center>The noise level in quarter is defined as the sum of the noise from all sources. To assess the quality of life of the population of the capital of Berland, it is required to find the number of quarters whose noise level exceeds the allowed level _p_.
## Input
The first line contains four integers _n_, _m_, _q_ and _p_ (1 ≤ _n_, _m_ ≤ 250, 1 ≤ _q_, _p_ ≤ 106) — the sizes of Berland's capital, the number of noise units that a quarter '_A_' produces, and the allowable noise level.
Each of the following _n_ lines contains _m_ characters — the description of the capital quarters, in the format that was described in the statement above. It is possible that in the Berland's capital there are no quarters of any type.
## Output
Print the number of quarters, in which the noise level exceeds the allowed level _p_.
[samples]
## Note
The illustration to the first example is in the main part of the statement.
Berland 的首都是一个由 n × m 个街区组成的矩形。所有街区分为三种类型：
标有字母 '_A_' 的街区产生 #cf_span[q] 单位的噪音。标有字母 '_B_' 的街区产生 #cf_span[2·q] 单位的噪音。以此类推，直到标有字母 '_Z_' 的街区，产生 #cf_span[26·q] 单位的噪音。城市中每种字母的街区数量可以是任意的。
当噪音从源头传播时，每经过一个与当前街区共享边的相邻街区，噪音水平减半（当奇数需要减半时，向下取整）。噪音沿路径传播。例如，如果某个街区距离噪音源的距离为 #cf_span[2]，则到达该街区的噪音值会被除以 #cf_span[4]。因此，从源头传播到某个街区的噪音水平仅由两者之间的最短路径长度决定。密集建设的街区是障碍物，噪音无法穿透它们。
一个街区的噪音水平定义为来自所有噪音源的噪音之和。为了评估 Berland 首都居民的生活质量，需要找出噪音水平超过允许水平 #cf_span[p] 的街区数量。
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[q] 和 #cf_span[p] (#cf_span[1 ≤ n, m ≤ 250], #cf_span[1 ≤ q, p ≤ 10^6]) —— 分别表示 Berland 首都的尺寸、字母 '_A_' 产生的噪音单位数，以及允许的噪音水平。
接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个字符 —— 描述首都街区的布局，格式如上所述。Berland 首都中可能不存在某种类型的街区。
请输出噪音水平超过允许水平 #cf_span[p] 的街区数量。
第一个示例的图示在题面主部分中给出。
## Input
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[q] 和 #cf_span[p] (#cf_span[1 ≤ n, m ≤ 250], #cf_span[1 ≤ q, p ≤ 10^6]) —— 分别表示 Berland 首都的尺寸、字母 '_A_' 产生的噪音单位数，以及允许的噪音水平。接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个字符 —— 描述首都街区的布局，格式如上所述。Berland 首都中可能不存在某种类型的街区。
## Output
请输出噪音水平超过允许水平 #cf_span[p] 的街区数量。
[samples]
## Note
第一个示例的图示在题面主部分中给出。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid.
Let $ q, p \in \mathbb{Z}^+ $ be the base noise unit and the allowed noise threshold.
Let $ G \in (\Sigma \cup \{*\})^{n \times m} $ be a grid, where each cell is either:
- A letter $ c \in \{A, B, \dots, Z\} $, representing a noise source producing $ 26 \cdot q $ units if $ c = Z $, $ 25 \cdot q $ if $ c = Y $, ..., $ 1 \cdot q $ if $ c = A $,
- Or $ * $, representing an obstacle (no noise propagation).
Let $ S \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the set of source cells: $ S = \{ (i,j) \mid G[i][j] \in \{A,\dots,Z\} \} $.
For each source $ s \in S $, let $ \text{noise}(s) = (G[s] - 'A' + 1) \cdot q $.
For any cell $ (i,j) $, let $ d(s, (i,j)) $ be the shortest Manhattan distance (number of steps through adjacent non-obstacle cells) from source $ s $ to $ (i,j) $, or $ \infty $ if unreachable.
The noise contributed by source $ s $ to cell $ (i,j) $ is:
$$
N_s(i,j) =
\begin{cases}
\left\lfloor \frac{\text{noise}(s)}{2^{d(s,(i,j))}} \right\rfloor & \text{if } d(s,(i,j)) < \infty \\
0 & \text{otherwise}
\end{cases}
$$
The total noise at cell $ (i,j) $ is:
$$
T(i,j) = \sum_{s \in S} N_s(i,j)
$$
**Constraints**
1. $ 1 \le n, m \le 250 $
2. $ 1 \le q, p \le 10^6 $
3. Obstacles ($ * $) block noise propagation.
4. Noise propagates only through adjacent (up/down/left/right) non-obstacle cells.
5. Noise is halved (rounded down) per unit distance.
**Objective**
Count the number of cells $ (i,j) $ such that $ T(i,j) > p $.