题目描述

潜水艇搁浅了。为了发现它，人们使用卫星数据；卫星能够高精度测量水面高度相对于平均海平面的偏差。

卫星获得的照片可以表示为一个数组，共有 $h$ 行，每行 $w$ 个元素。

在照片上建立坐标系：横轴沿照片行方向从左到右，纵轴沿照片列方向从下到上。

一个潜在的潜水艇图像是数组元素的一个集合，由以下几部分组成：

• “船体”：从坐标 $(x_1,y_1)$ 到 $(x_2,y_1)$ 的一条水平条带，其中 $x_1<x_2$；
• “指挥塔”：从坐标 $(x_3,y_1)$ 到 $(x_3,y_2)$ 的一条竖直条带，其中 $x_1\le x_3<x_2$，$y_1\le y_2$；
• “尾部”：从坐标 $(x_4,y_3)$ 到 $(x_4,y_4)$ 的一条竖直条带，其中 $x_3<x_4\le x_2$，$y_3\le y_1\le y_4$。

由于潜水艇位于接近水面的强流区域，潜水艇上方的水位会略微升高。因此，我们认为照片中“潜水艇图像”是所有潜在图像中，所含数组元素之和尽可能大的那一个。

请编写程序，找出照片中的潜水艇图像，并输出其元素和。

输入格式

为了压缩从卫星传输的数据，照片中的每个元素都用一个小写英文字母编码。

第一行包含整数 $k$（$k\le 26$），表示用于编码的字母数量。

第二行包含 $k$ 个整数 $C_i$，表示按英文字母顺序从第 $1$ 个字母到第 $k$ 个字母对应的高度偏差值。

第三行包含两个整数 $h,w$，表示照片大小。

接下来 $h$ 行，每行包含 $w$ 个字符，表示照片中各元素的编码值。

输出格式

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

样例 1

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

13

样例 1 的一种对应图像为：

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

样例 2

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

16

样例 2 的一种对应图像为：

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

样例 3

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

24

样例 3 的一种对应图像为：

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

样例 4

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

-2

样例 4 的一种对应图像为：

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

评分方式

本题共有四个子任务。只有通过某个子任务的所有测试点，才能获得该子任务的分数。

• 子任务 1（32 分）：$5\le h,w\le 10$，$|C_i|\le 10$；
• 子任务 2（22 分）：$5\le h,w\le 100$，$|C_i|\le 100$；
• 子任务 3（23 分）：$5\le h,w\le 500$，$|C_i|\le 500$；
• 子任务 4（23 分）：$5\le h,w\le 2000$，$|C_i|\le 2000$。