Подводная лодка

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

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

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