I love Ira#2853
Sasha wanted to make a very unusual birthday gift for Ira: a romantic message posted with solved problems on the most popular Ukrainian online judge. The problems on the site are arranged in a rectangular table, and solved problems are highlighted in a pleasant green. This inspired the idea to light up only those cells in the table that would form a desired image or inscription...
Even if the shape of the message is strictly defined, its position in the table can be controlled. Of course, the set of tasks that need to be solved depends on where the inscription is placed. Thus, Sasha assigned each task a score – an integer from to – and decided to choose the placement so that the sum of scores for the solved problems would be maximized. The text can be placed anywhere in the table, as long as the entire inscription lies within the table.
The first line contains two integers and (1 \le R, C \le 800) – the number of rows and columns in the table, respectively.
The next lines describe the map of problems. Each line contains exactly digits, representing the scores for the corresponding problems. The score for each problem is an integer from to .
The following line contains two integers (1 \le H \le R) and (1 \le W \le C) – the height and width of the inscription.
The next lines specify the template of the inscription. Each line contains characters: '#' means that the problem needs to be solved, '.' means that the problem should not be solved.
Print the maximum possible sum of the scores for the solved problems.
Example 1