Authentication Level

Time Limit : 1 sec, Memory Limit : 65536 KB

認証レベル

問題

あなたは 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 で表すことにする.

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

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

入力

入力ファイルのファイル名は input.txt である.
1 行目には正整数 R (1 ≤ R ≤ 100000) が書かれている.2 行目以降には,2 つの事務所のデータが順に与えられる.

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

また, RW1 × H1 + W2 × H2 を満たす.

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

出力

出力ファイルのファイル名は output.txt である. output.txt は,求める身分証の認証レベルの和の最小値のみを含む 1 行からなる.

入出力の例

例1

input.txt

5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3

output.txt

15

例2

input.txt

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

output.txt

4

例3

input.txt

6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 7

output.txt

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 個以上の部屋を訪れることができるための認証レベルの和の最小値である.

例 3 では,見学者に渡す身分証の認証レベルを,事務所 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 個以上の部屋を訪れることができるための認証レベルの和の最小値である.

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

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数の入力が与えられます. R が 0 のとき入力の終わりを示します.

Sample Input

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

Sample Output

15
4
9

Source: 8th Japanese Olympiad in Informatics , 2009-02-08
http://www.ioi-jp.org/