Задачи
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
В единственной строке вывести максимальную сумму оценок сложности решенных задач.
Входные данные #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