eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

I love Ira

I love Ira

Саша захотів зробити Ірі зовсім незвичний подарунок на День народження. Романтичне повідомлення, викладене розв'язаними задачами, на самому популярному українському сайті, присвяченому спортивному програмуванню. Задачі на сайті розміщуються у вигляді прямокутної таблиці, здані задачі підсвічуютбся приємним зеленим кольором. Це одного разу наштовхнуло на думку запалити у таблиці лише ті комірки, які б сформували задуману картинку, або напис... \includegraphics{https://static.e-olymp.com/content/f1/f1520a927121e2564be96ab52faa08f54f1f82dc.jpg} І якщо зі змістом повідомлення неоднозначностей не виникало, то його розміщенням у таблиці можна було керувати. Звичайно ж від місця розміщення напису залежало те, які задачі прийдеться розв'язуватиь. Тому Саша призначив кожній задачі оцінку складності --- число від \textbf{0} до \textbf{9}. І вирішив обрати таке розміщення, щоб сума оцінок розв'язаних ним задач була максимальною. Напис може розміщуватись у таблиці де завгодно, але лише щоб увесь шаблон знаходився в межах таблиці. \InputFile У першому рядку задано два числа \textbf{R} і \textbf{C} (\textbf{1} ≤ \textbf{R}, \textbf{C} ≤ \textbf{800}) --- кількість рядків та стоібців у таблиці. Далі в \textbf{R} рядках описаноа карту задач. У кожному рядку рівно по \textbf{C} символів --- складності задач. Складність задач вимірюється цифрою від \textbf{0} до \textbf{9}. У наступному рядку задано два числа \textbf{H} (\textbf{1} ≤ \textbf{H} ≤ \textbf{R}) і \textbf{W} (\textbf{1} ≤ \textbf{W} ≤ \textbf{C}) --- висота та ширина напису. Далі в \textbf{H} рядках задано шаблон напису. Кожен рядок складається з \textbf{W} символів: ’#’ означає необхідність розв'язання задачі, ’.’ означає, що задачу потрібно не розв'язувати. \OutputFile У єдиному рядку вивести максимальну суму оцінок складності розв'язани задач.
Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
22 18
000000000001000000
003001000000000000
000000000000000003
020000000010000000
090000000901000100
300400001911323500
000000000000000000
000000000000000000
000001000001000049
020100113210100000
200000006220004100
600009000217100009
000001000031004210
020101600100000190
110001002000000000
000092096071021990
000094000120010100
201003007430040300
100000010000100000
101040008000020001
404000000040043200
000000010000001000
17 18
###...#...........
.#....#...........
.#....#..#..#.#.##
.#....#.#.#.#.#.#.
.#....#.#.#.#.#.##
.#....#.#.#..#..#.
###...#..#...#..##
..................
..................
..................
..###.............
...#..............
...#..#.##.##.....
...#...#.#...#....
...#...#....##....
...#...#...#.#....
..###..#...##.#...
Вихідні дані #1
69