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