21504번 - Подводная лодка 서브태스크다국어

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из $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$ --- значения отклонений соответствующих каждому кодовому символу по порядку букв в английском алфавите от 1 до $k$-й.

Третья строка входных данных содержит числа $h$ и $w$ --- размеры снимка. Последующие $h$ строк содержат по $w$ символов --- кодовые значения элементов снимка.

Выходные данные должны содержать единственное целое число --- сумму элементов массива, соответствющих изображению подводной лодки.

• $5 \le h, w \le 2000$
• $| c_i | \le 2000$

Для примера ниже приведены несколько потенциальных изображений подводной лодки.

Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки: