CF847I.Noise Level

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.

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'.

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.

贝尔兰首都的形状为一个 $n \times m$ 的矩形街区网格。所有街区分为以下三类：

• 普通街区（用字符 . 表示）——此类街区本身不产生噪声，但也不阻碍噪声传播；
• 噪声源（用大写拉丁字母 'A' 到 'Z' 表示）——此类街区为噪声源，且不阻碍噪声传播；
• 高密度建筑区（用字符 '*' 表示）——此类街区具有隔音功能，噪声无法穿透其中，且自身构成噪声传播的障碍。

标有字母 'A' 的街区产生 $q$ 单位噪声；标有字母 'B' 的街区产生 $2\cdot q$ 单位噪声；依此类推，直至标有字母 'Z' 的街区产生 $26\cdot q$ 单位噪声。城市中每种字母标记的街区数量可以任意。

噪声从噪声源向外传播时，每移动到一个与之共边（即上下左右相邻）的街区，其强度减半（若当前值为奇数，则向下取整）。噪声沿路径链式传播。例如，若某街区与噪声源之间的最短距离为 $2$，则到达该街区的噪声值将被除以 $4$。因此，从某一噪声源传播至某街区的噪声强度，仅取决于二者之间的最短路径长度。高密度建筑区为障碍物，噪声无法穿透其中。

右侧表格中各单元格内的数值表示当 $q = 100$ 时对应街区的总噪声水平；每个和式中的第一项来自标有 'A' 的街区的噪声，第二项来自标有 'B' 的街区的噪声。

某街区的噪声水平定义为所有噪声源在该街区产生的噪声之和。为评估贝尔兰首都居民的生活质量，需计算噪声水平超过允许阈值 $p$ 的街区总数。

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.

第一行包含四个整数 $n$、$m$、$q$ 和 $p$（$1 ≤ n, m ≤ 250$，$1 ≤ q, p ≤ 10^6$）——分别表示 Berland 首都的尺寸、一个类型为 'A' 的街区所产生的噪声单位数，以及允许的噪声水平。

接下来的 $n$ 行，每行包含 $m$ 个字符——表示首都各街区的布局，格式如题面所述。Berland 首都中可能不存在任何类型的街区。

Print the number of quarters, in which the noise level exceeds the allowed level p.

输出噪声水平超过允许值 p 的季度数量。

The illustration to the first example is in the main part of the statement.

第一个示例的示意图位于题干的主体部分。