Problem:

Problem B: Yu-kun Likes Rectangles

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい長方形が大好きだ。そんなゆう君は３つの長方形を使って得点を得る新たな遊びを考え、得られる最大の得点を計算するためのプログラムを書くことにした。

Problem

H × W マスの長方形 A , B とh × w マスの長方形 C が与えられる。 ( H, Wはそれぞれ長方形A, Bの縦, 横のマスの数を, h, wはそれぞれ長方形Cの縦, 横のマスの数を表す )

図１のように A の各マスには整数が書かれており、Bの各マスには白または黒の色がついている。
Cの各マスにも同様に白または黒の色がついている。

図1

B の中に C と全く同じ模様の長方形があった場合、A の中でその長方形内に対応するマスに書かれている整数の和が得点として手に入る。

例えば図１のような長方形 A, B, C を使う場合、図２の赤線で示すように B の中に C と同じ模様が含まれているので、その場所から193点が得られる。

図2

B の中に C と全く同じ模様の長方形が１つ以上存在する場合、そのような長方形の中で最大何点を得ることができるだろうか？

ただし、B の中に C と同じ模様の長方形が存在しない場合は"NA” ( “ は除く ) と出力すること。
また、長方形を回転したり反転することはできない。

Input

入力の形式は以下の通りである。

H W
a(1,1) a(1,2) ... a(1,W)
a(2,1) a(2,2) ... a(2,W)
:
a(H,1) a(H,2) ... a(H,W)
b(1,1) b(1,2) ... b(1,W)
b(2,1) b(2,2) ... b(2,W)
:
b(H,1) b(H,2) ... b(H,W)
h w
c(1,1) c(1,2) ... c(1,w)
c(2,1) c(2,2) ... c(2,w)
:
c(h,1) c(h,2) ... c(h,w)

a(i,j) は長方形 A のマス (i, j) に書かれている整数を、b(i,j)は長方形 B のマス(i,j)の色を、c(i,j) は長方形 C のマス(i,j)の色を表す。
マスの色は0 が白、１ が黒を表す。

Constraints

入力は以下の条件を満たす。

入力は全て整数

1 ≤ H,W ≤ 50 

1 ≤ h ≤ H 

1 ≤ w ≤ W 

-100 ≤ a(i, j) ≤ 100 

b(i, j),c(i, j) は0か1

Output

長方形Bの中に長方形Cと全く同じ模様の場所が存在する場合、そのような場所の中でもっとも得点が高いものを出力せよ。

そのような場所が存在しない場合, “NA” ( “ は除く ) と出力せよ。

Sample Input 1

4 4
10 2 -1 6
8 1 -100 41
22 47 32 11
-41 99 12 -8
1 0 0 1
0 0 1 0
0 1 0 1
0 0 1 0
2 3
1 0 1
0 1 0

Sample Output 1

193

Sample Input 2

3 3
5 1 3
2 5 9
0 1 5
1 0 0
0 1 1
0 1 1
1 1
1

Sample Output 2

9

Sample Input 3

3 4
4 1 9 1
9 1 -1 3
2 -4 1 10
1 1 0 1
0 1 1 1
1 1 0 0
1 4
1 1 1 1

Sample Output 3

NA



Sample input:
4 4
10 2 -1 6
8 1 -100 41
22 47 32 11
-41 99 12 -8
1 0 0 1
0 0 1 0
0 1 0 1
0 0 1 0
2 3
1 0 1
0 1 0


Sample output:
193

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a_mp = [list(map(int, input().split())) for _ in range(H)]
b_mp = [list(map(int, input().split())) for _ in range(H)]
h, w = map(int, input().split())
c_mp = [list(map(int, input().split())) for _ in range(h)]
INF = 10 ** 20


def check(x, y):
  ret = 0
  for dy in range(h):
    for dx in range(w):
      if b_mp[y + dy][x + dx] != c_mp[dy][dx]:
        return -INF
      ret += a_mp[y + dy][x + dx]
  return ret


ans = -INF
for y in range(H - h + 1):
  for x in range(W - w + 1):
    ans = max(ans, check(x, y))
if ans == -INF:
  print("NA")
else:
  print(ans)