Berland 的首都呈矩形,大小为 n × m 四分之一。所有宿舍分为三种类型:
- 常规(标有字符“.”)——此类区域不会产生噪音,但不会成为噪音传播的障碍;
- 噪声源(用从“A”到“Z”的大写拉丁字母标记)——此类区域是噪声源,并且不会阻碍噪声传播;
- 建筑密集(标有字符“*”)——此类宿舍是隔音的,噪音不会渗透到其中,而且它们本身就是噪音传播的障碍。
标有字母“A”的四分之一产生 q 单位的噪声。标有字母“B”的四分之一产生 2·q 单位的噪声。依此类推,最多四分之一标有字母“Z”,它产生 26·q 单位的噪声。城市中可以有任意数量的用每个字母标记的街区。
当从噪声源传播时,当从四分之一移动到与其共享一侧的四分之一时,噪声级别会减半(当奇数要减半时,会向下舍入)。噪音沿着链条传播。例如,如果某个四分之一区距噪声源的距离为 2,则到达该四分之一区的噪声值将除以 4。因此,从源到该四分之一区的噪声级别仅由它们之间的最短路径长度决定。建筑密集的住宅区是障碍物,噪音无法渗透到其中。
右侧表格单元格中的值显示 q = 100 时各个季度的总噪声水平,每个总和中的第一项是来自季度“A”的噪声,第二项是来自季度“B”的噪声。
四分之一的噪声水平定义为所有源噪声的总和。为了评估贝尔兰首都居民的生活质量,需要找出噪音水平超过允许水平 p 的小区数量。
输入
第一行包含四个整数 n、m、q 和 p(1 ≤ n、m ≤ 250、1 ≤ q、p ≤ 106)——Berland 首都的大小、四分之一“A”产生的噪音单位数量以及允许的噪音水平。
以下 n 行中的每一行都包含 m 个字符 - 对首都地区的描述,采用上面语句中描述的格式。贝尔兰首都可能没有任何类型的宿舍。
输出
打印噪音水平超过允许水平的季度数 p。
示例
输入 #1
3 3 100 140 ... A*. .B.
输出 #1
3
输入 #2
3 3 2 8 B*. BB* BBB
输出 #2
4
输入 #3
3 4 5 4 ..*B ..** D...
输出 #3
7
注意
第一个示例的说明位于语句的主要部分。