会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい長方形が大好きだ。そんなゆう君は3つの長方形を使って得点を得る新たな遊びを考え、得られる最大の得点を計算するためのプログラムを書くことにした。
H × W マスの長方形 A , B とh × w マスの長方形 C が与えられる。 ( H, Wはそれぞれ長方形A, Bの縦, 横のマスの数を, h, wはそれぞれ長方形Cの縦, 横のマスの数を表す )
図1のように A の各マスには整数が書かれており、Bの各マスには白または黒の色がついている。 Cの各マスにも同様に白または黒の色がついている。
B の中に C と全く同じ模様の長方形があった場合、A の中でその長方形内に対応するマスに書かれている整数の和が得点として手に入る。
例えば図1のような長方形 A, B, C を使う場合、図2の赤線で示すように B の中に C と同じ模様が含まれているので、その場所から193点が得られる。
B の中に C と全く同じ模様の長方形が1つ以上存在する場合、そのような長方形の中で最大何点を得ることができるだろうか?
ただし、B の中に C と同じ模様の長方形が存在しない場合は"NA” ( “ は除く ) と出力すること。 また、長方形を回転したり反転することはできない。
入力の形式は以下の通りである。
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 が白、1 が黒を表す。
入力は以下の条件を満たす。
長方形Bの中に長方形Cと全く同じ模様の場所が存在する場合、そのような場所の中でもっとも得点が高いものを出力せよ。
そのような場所が存在しない場合, “NA” ( “ は除く ) と出力せよ。
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
193
3 3 5 1 3 2 5 9 0 1 5 1 0 0 0 1 1 0 1 1 1 1 1
9
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
NA