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

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

1 секунда
512 мегабайтів
Середня

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

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

- "корпус" - полоса з елементів з координатами від (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) - кількість використаних для кодування букв. Другий рядок вхідних даних містить цілих чисел C_{i} - значення відхилень, які відповідають кожному кодовому символу по порядку букв в англійському алфавіті від 1 до -ї.

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Приклад 4

Loading
Loading

Примітка

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

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

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

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

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

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

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

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

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

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

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

Оцінювання

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

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