Deskripsi Masalah

Apakah Anda mengenal perusahaan Just Odd Inventions? Bisnis dari perusahaan ini adalah membuat "penemuan yang aneh saja (just odd inventions)". Di sini kita menyebutnya secara singkat sebagai Perusahaan JOI.

Perusahaan JOI memiliki $2$ kantor, dan masing-masing kantor terdiri dari ruangan-ruangan persegi berukuran sama yang tersusun dalam bentuk kisi-kisi. Di antara setiap pasang ruangan yang bersisian pada tepinya, terdapat sebuah pintu yang dilengkapi dengan fungsi autentikasi menggunakan kartu identitas. Karena Perusahaan JOI menangani informasi rahasia dari berbagai tingkatan, sebuah bilangan bulat positif yang disebut level kerahasiaan ditetapkan untuk setiap ruangan, dan seseorang tidak dapat memasuki ruangan tersebut kecuali level autentikasi berupa bilangan bulat non-negatif yang ditetapkan untuk kantor tersebut pada kartu identitas nilainya lebih besar atau sama dengan level kerahasiaan ruangan itu. Satu-satunya pintu masuk/keluar di setiap kantor hanyalah lobi lift tunggal, dan level kerahasiaan ruangan lobi lift adalah yang terendah, yaitu $1$. Ketika level autentikasi untuk kantor tersebut adalah $0$, seseorang bahkan tidak dapat memasuki lobi lift.

Di Perusahaan JOI, karena usulan mendadak dari presiden direktur, diputuskan untuk mengadakan tur bagi masyarakat umum untuk mengunjungi bagian dalam perusahaan. Anda perlu menentukan kombinasi level autentikasi pada kartu identitas yang akan diberikan kepada pengunjung. Setiap kali pengunjung menemukan pintu yang dapat dibuka, mereka pasti akan membukanya dan masuk ke dalam (mengunjungi ruangan yang sama berkali-kali juga dimungkinkan). Oleh karena itu, Anda tidak ingin membuat level autentikasi pada kartu identitas pengunjung lebih tinggi dari yang diperlukan. Namun, agar tur tersebut menarik, tur harus memungkinkan pengunjung untuk mengunjungi setidaknya $R$ ruangan secara total di $2$ kantor, termasuk ruangan lobi lift. Jika level autentikasi pada kartu identitas diatur terlalu rendah, kondisi ini mungkin tidak dapat dipenuhi.

Perusahaan JOI memiliki $2$ kantor, dan ruangan-ruangan di kantor ke-$k$ ($k = 1, 2$) tersusun sebanyak $W_k$ ruangan dalam arah timur-barat dan $H_k$ ruangan dalam arah utara-selatan, sehingga totalnya ada $W_k \times H_k$ ruangan. Ruangan ke-$i$ dari barat dan ke-$j$ dari utara di kantor ke-$k$ dinyatakan dengan $(i, j)_k$.

Diberikan nilai $W_k$, $H_k$, dan $R$, posisi lobi lift $(X_k, Y_k)_k$, serta level kerahasiaan masing-masing ruangan, buatlah program untuk mencari nilai minimum dari jumlah level autentikasi pada kartu identitas pengunjung agar pengunjung dapat mengunjungi setidaknya $R$ ruangan secara total di $2$ kantor.

Ngomong-ngomong, bagaimana Perusahaan JOI mendapatkan keuntungan dengan membuat "penemuan yang aneh saja" adalah rahasia tertinggi bahkan di dalam perusahaan, dan tidak ada seorang pun yang tahu selain presiden direktur.

Format Masukan

• Baris ke-$1$ berisi sebuah bilangan bulat positif $R$ ($1 \le R \le 100000$).
• Mulai baris ke-$2$ dan seterusnya, data untuk $2$ kantor diberikan secara berurutan.
• Data untuk masing-masing kantor diawali dengan bilangan bulat positif $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$) pada baris pertama, diikuti oleh $H_k$ baris di mana bilangan ke-$i$ pada baris ke-$j$ adalah bilangan bulat $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) yang menyatakan level kerahasiaan ruangan $(i, j)_k$.
• Selain itu, berlaku $R \le W_1 \times H_1 + W_2 \times H_2$.

Dari data uji, untuk $30\%$ nilai, berlaku $R, W_k, H_k \le 100$.

Format Keluaran

Keluarkan $1$ baris yang hanya berisi nilai minimum dari jumlah level autentikasi kartu identitas yang dicari.

Sample 1

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

15

Sample 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 6

4

Sample 3

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

9

Penjelasan Contoh

Pada Contoh 1, jika level autentikasi pada kartu identitas yang diberikan kepada pengunjung diatur sehingga level autentikasi untuk Kantor $1$ adalah $9$ dan level autentikasi untuk Kantor $2$ adalah $6$, maka pengunjung dapat mengunjungi $5$ ruangan (ruangan $(1, 1)_1, (1, 2)_1, (2, 1)_1$ di Kantor $1$, serta ruangan $(1, 1)_2, (2, 1)_2$ di Kantor $2$). Pada saat ini, jumlah level autentikasinya adalah $15$. Ini adalah nilai minimum dari jumlah level autentikasi agar dapat mengunjungi total setidaknya $5$ ruangan.

Pada Contoh 3, jika level autentikasi pada kartu identitas yang diberikan kepada pengunjung diatur sehingga level autentikasi untuk Kantor $1$ adalah $9$ dan level autentikasi untuk Kantor $2$ adalah $0$, maka pengunjung dapat mengunjungi $9$ ruangan (ruangan $(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$ di Kantor $1$). Tidak ada $1$ ruangan pun di Kantor $2$ yang dapat dikunjungi (bahkan tidak dapat memasuki lobi lift $(1, 1)_2$). Pada saat ini, jumlah level autentikasinya adalah $9$. Ini adalah nilai minimum dari jumlah level autentikasi agar dapat mengunjungi total setidaknya $6$ ruangan.