Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(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\) символов — кодовые значения элементов снимка.
Выходные данные
Выходные данные должны содержать единственное целое число — сумму элементов массива, соответствющих изображению подводной лодки.
Примеры
| № |
Входные данные |
Выходные данные |
Изображение |
| 1 |
2
-10 1
6 11
aaaaaaaaaaa
aaabaaaaaaa
aaabaaaabaa
abbbbbbbbba
aaaaaaaabaa
aaaaaaaaaaa |
13 |
...........
...b.......
...b....b..
.bbbbbbbbb.
........b..
...........
|
| 2 |
3
-4 -3 4
5 5
bbabc
ccaac
accba
baccb
baaaa |
16 |
.....
.c...
.cc..
..c..
.....
|
| 3 |
3
-2 4 0
5 5
abccb
cccac
cbcba
cccbb
accba |
24 |
.b...
.c...
.b.b.
cccbb
...b.
|
| 4 |
4
-1 -5 -3 0
5 5
bbabc
ccaac
acdba
baccb
baaaa |
-2 |
.....
..aa.
.....
.....
.....
|
Пояснение
Для примера ниже приведены несколько потенциальных изображений подводной лодки.
Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки:
