题目背景

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

题目描述

一艘潜艇搁浅在浅海海底。为了探测其位置，科学家使用了卫星数据——卫星可以高精度地测量海面相对于平均海平面的高度偏差。卫星拍摄的图像可以表示为一个包含 $h$ 行、每行 $w$ 个元素的数组。

:::align{center} :::

在该图像上建立坐标系：横坐标轴（$x$ 轴）沿行方向，从左向右；纵坐标轴（$y$ 轴）沿列方向，从下向上。

潜艇的潜在图像定义为由以下部分组成的元素集合：

• “艇身”：由坐标从 $(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$ —— 分别表示前 $k$ 个英文字母（从 a 开始）的高度偏差值。
• 第三行包含两个整数 $h$ 和 $w$ —— 图像的行数与列数。
• 接下来的 $h$ 行中，每行包含 $w$ 个字符，表示图像的编码内容。

输出格式

输出一个整数 —— 对应于潜艇图像的数组元素之和的最大可能值。

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

13

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

16

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

24

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

-2

提示

样例解释

样例 1-4 的图像分别如下：

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

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

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

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

下面展示了几个潜在的潜艇图像示例：

:::align{center} :::

以下是一些不是潜在潜艇图像的示例：

:::align{center} :::

评分标准

子任务编号	分值	$h, w$ 范围	$|c_i|$ 范围
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		$5 \le h, w \le 2000$	$|c_i| \le 2000$