P14267 [ROI 2015 Day2] 潜水艇

**译自 [ROI 2015](https://neerc.ifmo.ru/school/archive/2014-2015.html) Day2 T2.** ***[Подводная лодка](https://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-roi-2015-day2.pdf)***

一艘潜艇搁浅在浅海海底。为了探测其位置，科学家使用了卫星数据——卫星可以高精度地测量海面相对于平均海平面的高度偏差。卫星拍摄的图像可以表示为一个包含 $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$ 个字符，表示图像的编码内容。

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

### 样例解释 样例 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 | 23 | $5 \le h, w \le 2000$ | $\|c_i\| \le 2000$ |