Problema

¿Conoces la empresa Just Odd Inventions? La actividad de esta empresa consiste en hacer «solo inventos extraños (just odd inventions)». Aquí la llamaremos abreviadamente la empresa JOI.

La empresa JOI tiene $2$ oficinas, y cada una está formada por habitaciones cuadradas del mismo tamaño dispuestas en forma de cuadrícula. Entre cada par de habitaciones que comparten un lado hay una puerta equipada con una función de autenticación mediante tarjeta de identificación. Dado que la empresa JOI maneja información confidencial de diversos niveles, cada habitación tiene asignado un entero positivo llamado nivel de confidencialidad, y no se puede entrar en una habitación a menos que el nivel de autenticación (un entero no negativo establecido en la tarjeta de identificación para cada oficina) sea mayor o igual que el nivel de confidencialidad de esa habitación. La única entrada/salida de cada oficina es su único vestíbulo de ascensores, y el nivel de confidencialidad de la habitación del vestíbulo de ascensores es el mínimo, que es $1$. Cuando el nivel de autenticación para esa oficina es $0$, ni siquiera se puede entrar en el vestíbulo de ascensores.

En la empresa JOI, debido a una repentina propuesta del presidente, se decidió realizar un recorrido turístico para que el público general visite el interior de la empresa. Debes decidir la combinación de niveles de autenticación de la tarjeta de identificación que se entregará a los visitantes. Siempre que un visitante encuentra una puerta que puede abrirse, la abre sin falta y entra (también es posible visitar la misma habitación varias veces). Por ello, no quieres que el nivel de autenticación de la tarjeta de identificación de los visitantes sea más alto de lo necesario. Sin embargo, para que el recorrido resulte atractivo, es necesario que en el recorrido se puedan visitar en total al menos $R$ habitaciones entre las $2$ oficinas, incluyendo las habitaciones de los vestíbulos de ascensores. Si reduces demasiado el nivel de autenticación de la tarjeta de identificación, es posible que no se pueda cumplir esta condición.

La empresa JOI tiene $2$ oficinas, y las habitaciones de la $k$-ésima oficina ($k = 1, 2$) están dispuestas en $W_k$ habitaciones en dirección este-oeste y $H_k$ habitaciones en dirección norte-sur, haciendo un total de $W_k \times H_k$ habitaciones. Representaremos por $(i, j)_k$ la $i$-ésima habitación desde el oeste y $j$-ésima desde el norte en la $k$-ésima oficina.

Dados los valores de $W_k$, $H_k$ y $R$, la posición del vestíbulo de ascensores $(X_k, Y_k)_k$ y el nivel de confidencialidad de cada habitación, escribe un programa para hallar el valor mínimo posible de la suma de los niveles de autenticación de la tarjeta de identificación de los visitantes para que puedan visitar al menos $R$ habitaciones en total entre las $2$ oficinas.

Por cierto, cómo obtiene beneficios la empresa JOI haciendo «solo inventos extraños» es alto secreto incluso dentro de la propia empresa, y nadie lo sabe salvo el presidente.

Entrada

• En la $1$-a línea hay un entero positivo $R$ ($1 \le R \le 100000$).
• A partir de la $2$-a línea se proporcionan en orden los datos de las $2$ oficinas.
• Los datos de cada oficina se dan con los enteros positivos $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$) en la primera línea, seguidos de $H_k$ líneas donde el $i$-ésimo número de la $j$-ésima línea es un entero $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) que representa el nivel de confidencialidad de la habitación $(i, j)_k$.
• Además, se cumple $R \le W_1 \times H_1 + W_2 \times H_2$.

De los datos de prueba, para el $30\%$ de la puntuación se cumple $R, W_k, H_k \le 100$.

Salida

Imprime $1$ sola línea que contenga únicamente el valor mínimo buscado de la suma de los niveles de autenticación de la tarjeta de identificación.

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

Explicación de los ejemplos

En el Ejemplo 1, si los niveles de autenticación de la tarjeta de identificación entregada a los visitantes se configuran de modo que el nivel de autenticación de la Oficina $1$ sea $9$ y el de la Oficina $2$ sea $6$, los visitantes pueden visitar $5$ habitaciones (las habitaciones $(1, 1)_1, (1, 2)_1, (2, 1)_1$ de la Oficina $1$, y las habitaciones $(1, 1)_2, (2, 1)_2$ de la Oficina $2$). En este caso, la suma de los niveles de autenticación es $15$. Este es el valor mínimo de la suma de los niveles de autenticación necesario para poder visitar al menos $5$ habitaciones en total.

En el Ejemplo 3, si los niveles de autenticación de la tarjeta de identificación entregada a los visitantes se configuran de modo que el nivel de autenticación de la Oficina $1$ sea $9$ y el de la Oficina $2$ sea $0$, los visitantes pueden visitar $9$ habitaciones (las habitaciones $(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$ de la Oficina $1$). No pueden visitar ni $1$ sola habitación de la Oficina $2$ (ni siquiera pueden entrar al vestíbulo de ascensores $(1, 1)_2$). En este caso, la suma de los niveles de autenticación es $9$. Este es el valor mínimo de la suma de los niveles de autenticación necesario para poder visitar al menos $6$ habitaciones en total.