eolymp
bolt
Try our new interface for solving problems
Problems

I love Ira

I love Ira

Sasha wanted to make Ira a very unusual birthday gift. Romantic message posted with solved problems, on the most popular Ukrainian online judge. Problems on the site are in the form of a rectangular table, solved problems are highlighted in a pleasant green. This has suggested the idea to light in the table only those cells that would form a desired image or inscription... \includegraphics{https://static.e-olymp.com/content/4c/4c23fd3a6155444997e8341da34bf469c6dd1b13.jpg} Even if the shape of the message is strictly defined, its position in the table can be controlled. Of course, on the location of the signs depends set of tasks to be solved. So Sasha has assigned to each task a score - a integer from \textbf{0} to \textbf{9}, and decided to location in such way, so that the sum of marks would be maximial. Text can be placed in a table anywhere, with only one limitation: inscription must entirely lie in the table. \InputFile First line of the input file contain two integers \textbf{R} and \textbf{C} (\textbf{1} ≤ \textbf{R}, \textbf{C} ≤ \textbf{800}) --- number of rows and columns in the table, respectively. In next \textbf{R} lines map of the problems is described. Each line has exactly \textbf{C} digits - score for corresponding tasks. The score for the task is measured by the integer from \textbf{0} to \textbf{9}. The next line gives two numbers \textbf{H} (\textbf{1} ≤ \textbf{H} ≤ \textbf{R}) and \textbf{W} (\textbf{1} ≤ \textbf{W} ≤ \textbf{C}) --- height and width of the inscription, respectively. In next \textbf{H} lines template of the inscription is given. Each line consists of \textbf{W} characters: ’#’ means that the problem needs to be solved, ’.’ means that the problem should not be solved. \OutputFile Print the maximum sum of scores for solved problems.
Time limit 3 seconds
Memory limit 256 MiB
Input example #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
###...#...........
.#....#...........
.#....#..#..#.#.##
.#....#.#.#.#.#.#.
.#....#.#.#.#.#.##
.#....#.#.#..#..#.
###...#..#...#..##
..................
..................
..................
..###.............
...#..............
...#..#.##.##.....
...#...#.#...#....
...#...#....##....
...#...#...#.#....
..###..#...##.#...
Output example #1
69