题目描述

译自 ROI 2015 Day2 T2. Подводная лодка

一艘潜水艇在浅水区搁浅。为了探测其位置，使用了卫星数据，卫星能够高精度测量水面高度相对于平均海平面的偏差。卫星获取的图像是一个包含 $h$ 行、每行 $w$ 个元素的数组。

在图像上引入一个坐标系，其中横轴沿图像行从左至右，纵轴沿图像列从下至上。潜水艇的潜在图像由数组中的一组元素组成，包括以下部分：

• 艇身：从坐标 $(x_1, y_1)$ 到 $(x_2, y_1)$ 的元素条带，其中 $x_1 < x_2$；
• 指挥塔：从坐标 $(x_3, y_1)$ 到 $(x_3, y_2)$ 的元素条带，其中 $x_1 \leq x_3 < x_2$，$y_1 \leq y_2$；
• 尾部：从坐标 $(x_4, y_3)$ 到 $(x_4, y_4)$ 的元素条带，其中 $x_3 < x_4 \leq x_2$，$y_3 \leq y_1 \leq y_4$。

由于潜水艇靠近水面，且所在区域有强流，水面高度在其上方略有升高。因此，图像上潜水艇的图像被定义为具有最大可能元素和的潜在图像。

你的任务是编写一个程序，在图像上找到潜水艇的图像，并输出其元素之和。

输入格式

为了压缩卫星传输的数据，图像的每个元素用小写英文字母编码。输入数据的第一行包含一个整数 $k$，表示用于编码的字母数量（$k \le 26$）。

第二行包含 $k$ 个整数 $c_i$，表示对应于英文字母表中前 $k$ 个字母的偏差值。

第三行包含两个整数 $h$ 和 $w$，表示图像的尺寸。

接下来的 $h$ 行，每行包含 $w$ 个字符，表示图像元素的编码值。

输出格式

输出一行，包含一个整数，表示对应潜水艇图像的数组元素之和。

2
-10 1
6 11
aaaaaaaaaaa
aaabaaaaaaa
aaabaaaabaa
abbbbbbbbba
aaaaaaaabaa
aaaaaaaaaaa

13

图像如下：

...........
...b.......
...b....b..
.bbbbbbbbb.
........b..
...........

3
-4 -3 4
5 5
bbabc
ccaac
accba
baccb
baaaa

16

图像如下：

.....
.c...
.cc..
..c..
.....

3
-2 4 0
5 5
abccb
cccac
cbcba
cccbb
accba

24

图像如下：

.b...
.c...
.b.b.
cccbb
...b.

4
-1 -5 -3 0
5 5
bbabc
ccaac
acdba
baccb
baaaa

-2

图像如下：

.....
..aa.
.....
.....
.....

样例解释

以下是为样例提供的几个潜水艇潜在图像。

以下是图像上的几个元素集合，它们不是潜水艇的潜在图像。

数据范围与提示

详细子任务附加限制及分值如下表所示：