題目描述
你知道 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 \times H_k$ 個房間。我們將從西數起第 $i$ 個、從北數起第 $j$ 個房間表示為 $(i, j)_k$。
給定 $W_k$、$H_k$ 與 $R$ 的值、電梯大廳的位置 $(X_k, Y_k)_k$ 以及各房間的機密等級，請撰寫程式，求出為使參觀者能在 $2$ 個事務所合計造訪至少 $R$ 個房間，參觀者身分證的認證等級之和的最小值。
順帶一提，JOI 公司究竟是如何靠做「只是很奇妙的發明」來獲利的，即便在公司內部也是最高機密，除了社長之外無人知曉。
輸入格式
- 第 $1$ 行包含一個正整數 $R$（$1 \le R \le 100000$）。
- 第 $2$ 行起，依次給出 $2$ 個事務所的資料。
- 每個事務所的資料中，第一行為正整數 $W_k, H_k, X_k, Y_k$（$1 \le X_k \le W_k \le 500, 1 \le Y_k \le H_k \le 500$），接下來的 $H_k$ 行中，第 $j$ 行的第 $i$ 個數為表示房間 $(i, j)_k$ 的機密等級的整數 $L_{k, i, j}$（$1 \le L_{k, i, j} < 100000000 = 10^8$）。
- 此外，滿足 $R \le W_1 \times H_1 + W_2 \times H_2$。
在測試資料中，佔總分 $30\%$ 的部分滿足 $R, W_k, H_k \le 100$。
輸出格式
輸出僅一行，只包含所求的身分證認證等級之和的最小值。
Sample 1
5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 315Sample 2
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 64Sample 3
6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 79範例說明
在範例 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$ 個房間所需的認證等級之和的最小值。
