Підводний човен#162

Підводний човен

1 second
512 megabytes
Medium

Підводний човен сів на мілину. Для його виявлення використовують дані супутника, який з високою точністю вимірює відхилення висоти поверхні води від середнього рівня моря. Знімок, отриманий із супутника, представляє собою масив з рядків по елементів у кожному рядку.

Введемо на знімку систему координат з віссю абсцис, яка напрямлена вздовж рядків знімку зліва направо, і віссю ординат, напрямленій вздовж стовпців знизу догори. Потенційне зображення підводного човна представляє собою множину елементів масиву, що складається з наступних частин:

- "корпус" - полоса з елементів з координатами від (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}.

Оскільки підводний човен знаходиться поблизу поверхні в районі з сильною течією, рівень води над ним трохи підвищується. Тому зображенням підводного човна на знімку будемо вважати зображення з максимально можливою сумою елементів масиву, що входять в нього.

Напишіть програму, яка знаходить на знімку зображення підводного човна і виводе суму його елементів.

Input

Для стиснення даних, що передаються з супутника, кожен елемент знімка кодується маленькою буквою англійського алфавіту. Перший рядок вхідних даних містить число k (k \le 26) - кількість використаних для кодування букв. Другий рядок вхідних даних містить цілих чисел C_{i} - значення відхилень, які відповідають кожному кодовому символу по порядку букв в англійському алфавіті від 1 до -ї.

Третій рядок вхідних даних містить числа i - розміри знімка. Наступні рядків містять по символів - кодові значення елементів знімка.

Output

У вихідний файл виведіть одне число - суму елементів масива, що відповідають зображенню підводного човна.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Note

Для прикладу ничже наведено кілька потенційних зображень підводного човна.

Нижче наведено кілька множин елементів знімка, які не є потенційними зображеннями підводного човна:

Пояснення до прикладів:

Зображення для першого прикладу

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

Зображення для другого прикладу

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

Зображення для третього прикладу

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

Зображення для четвертого прикладу

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

Scoring

В даній задачі чотири підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.

Підзадача 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

Підзадача 3 (23 балів):

5 \le h, w \le 2000, |C_{i}| \le 2000