5574번 - 認証レベル 다국어

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

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

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

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

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

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

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

事務所のデータは，最初の行に正整数 W_k, H_k, X_k, Y_k (1 ≤ X_k ≤ W_k ≤ 500, 1 ≤ Y_k ≤ H_k ≤ 500) ，続く H_k 行の j 行目の i 番目に，部屋 (i, j)_k の機密レベルを表す整数 L_k,i,j (1 ≤ L_k,i,j < 100000000 = 10⁸) として与えられる．

また，R ≤ W₁ × H₁ + W₂ × H₂ を満たす．

求める身分証の認証レベルの和の最小値のみを含む1行からなる．

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

事務所 1 (認証レベル 9)	事務所 2 (認証レベル 6)

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

事務所 1 (認証レベル 9)	事務所 2 (認証レベル 0)