Pattern Matching#5951
Sign in

Pattern Matching

8 seconds
512 megabytes
Very hard

You are given a rectangular table A of size R \times C, filled with digits (a_{ij} for 0 \leq i < R, 0 \leq j < C). Additionally, you are given a table B of size H \times W, filled with zeros and ones (b_{ij} for 0 \leq i < H, 0 \leq j < W).

Your task is to find the maximum value of the following function for two variables and :

\text{cost}(x, y) = \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} a_{x+i, ~ y+j} \cdot b_{ij}

where 0 \leq x \leq R-H and 0 \leq y \leq C-W.

Input

The first line contains two integers and (1 \leq R, C \leq 800). Each of the next lines contains characters, the elements of table A (0 \leq a_{ij} \leq 9).

The next line contains two integers and (1 \leq H \leq R, 1 \leq W \leq C). Each of the following lines contains characters, the elements of table B. Each character is either or .

Output

Print the maximum value of the function cost.

Examples

Example 1

Loading
Loading