認証レベル

問題

あなたは Just Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.

JOI 社には 2 つの事務所があり,それぞれ同じ大きさの正方形の部屋がマス目状に並んでできている.辺で接しているすべての部屋の間に,身分証による認証機能の付いた扉がある.JOI 社では様々なレベルの機密情報を扱っているため,部屋ごとに機密レベルという正の整数が設定されており,身分証の事務所ごとに定められた非負整数の認証レベルが,機密レベル以上でないとその部屋に入室することができない.各事務所の出入り口は唯一あるエレベーターホールのみで,エレベーターホールの部屋の機密レベルは最低の 1 である.その事務所についての認証レベルが 0 のときはエレベーターホールに入ることさえできない.

JOI 社では,社長の突発的な提案で,一般の人に社内を見学してもらうツアーを実施することになった.あなたは見学者に渡す身分証の認証レベルの組み合わせを決める必要がある.見学者は開けられる扉を見つけると必ず開けて中に入る (同じ部屋を何度も訪れることも可能である).そのため,必要以上に見学者の身分証の認証レベルを高くしたくはない.しかし,ツアーに魅力を持たせるため,ツアーではエレベーターホールの部屋を含め 2 つの事務所であわせて R 個以上の部屋を訪れることができるようにする必要がある.身分証の認証レベルを低くしすぎると,この条件を満たすことができないかもしれない.

JOI 社には事務所が 2 個あり,第 k 事務所 (k = 1, 2) の部屋は東西方向に Wk 個,南北方向に Hk 個並んでおり,全部で Wk × Hk 個ある. 西から i 番目,北から j 番目の部屋を (i, j)k で表すことにする.

Wk と Hk と R の値,エレベーターホールの位置 (Xk, Yk )k ,各部屋の機密レベルが与えられたとき,見学者が 2 つの事務所であわせて R 個以上の部屋を訪れることができるための,見学者の身分証の認証レベルの和の最小値を求めるプログラムを作成せよ.

なお,JOI 社が「ただ奇妙な発明」をすることでどうやって利益を得ているかは,社内でも最高機密であり社長以外の誰も知らない.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

1 行目には正整数 R (1 ≤ R ≤ 100000) が書かれている.2 行目以降には,2 つの事務所のデータが順に与えられる.

事務所のデータは,最初の行に正整数 Wk, Hk, Xk, Yk (1 ≤ Xk ≤ Wk ≤ 500, 1 ≤ Yk ≤ Hk ≤ 500), 続く Hk 行の j 行目の i 番目に, 部屋 (i, j)k の機密レベルを表す整数 Lk, i,j (1 ≤ Lk,i,j < 100000000 = 108) として与えられる.

また, R ≤ W1 × H1 + W2 × H2 を満たす.

採点用データのうち, 配点の 30% 分については, R, Wk, Hk ≤ 100 を満たす.

R が 0 のとき入力の終了を示す.　データセットの数は 10 を超えない．

出力

データセットごとに,求める身分証の認証レベルの和の最小値を 1 行に出力する.

入出力例

入力例

5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3
8
5 4 1 3
5 5 4 5 5
8 2 1 9 7
1 1 3 5 1
7 2 7 1 3
6 5 6 2
2 3 5 8 2 7
1 6 9 4 5 1
2 4 5 4 2 2
5 4 2 5 3 3
7 1 5 1 5 6
6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 7
0

出力例

15
4
9

1つ目の例 では,見学者に渡す身分証の認証レベルを,事務所 1 の認証レベルが 9,事務所 2 の認証レベルが 6 となるように設定すると,見学者は 5 個の部屋 (事務所 1 の部屋 (1, 1)1 , (1, 2)1 , (2, 1)1 と,事務所 2 の部屋 (1, 1)2 , (2, 1)2 ) を訪れることができる.このとき,認証レベルの和は 15 となる.これが合計 5 個以上の部屋を訪れることができるための認証レベルの和の最小値である.


３つ目の例 では,見学者に渡す身分証の認証レベルを,事務所 1 の認証レベルが 9,事務所 2 の認証レベルが 0 となるように設定すると,見学者は 9 個の部屋 (事務所 1 の部屋 (1, 1)1, (1, 2)1, (1, 3)1, (2, 1)1, (2, 2)1, (2, 3)1, (3, 1)1, (3, 2)1, (3, 3)1 ) を訪れることができる.事務所 2 の部屋は 1 個も訪れることができない.(エレベーターホール (1, 1)2にすら入ることができない.) このとき,認証レベルの和は 9 となる.これが合計 6 個以上の部屋を訪れることができるための認証レベルの和の最小値である.


上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。