Problema

Conosci l'azienda Just Odd Inventions? L'attività di questa azienda consiste nel realizzare «solo strane invenzioni (just odd inventions)». Qui la chiameremo brevemente l'azienda JOI.

L'azienda JOI possiede $2$ uffici, e ciascuno è formato da stanze quadrate della stessa dimensione disposte a griglia. Tra tutte le coppie di stanze adiacenti lungo un lato si trova una porta dotata di una funzione di autenticazione tramite tesserino identificativo. Poiché l'azienda JOI tratta informazioni riservate di vari livelli, per ciascuna stanza è fissato un intero positivo chiamato livello di riservatezza, e non è possibile entrare in una stanza a meno che il livello di autenticazione (un intero non negativo stabilito sul tesserino per quell'ufficio) sia maggiore o uguale al livello di riservatezza della stanza. L'unico ingresso/uscita di ciascun ufficio è l'unico atrio degli ascensori, e il livello di riservatezza della stanza dell'atrio degli ascensori è il minimo, vale a dire $1$. Quando il livello di autenticazione per quell'ufficio è $0$, non è possibile nemmeno entrare nell'atrio degli ascensori.

Nell'azienda JOI, su proposta improvvisa del presidente, si è deciso di organizzare un tour per consentire al pubblico di visitare l'interno dell'azienda. Devi decidere la combinazione dei livelli di autenticazione sul tesserino da consegnare ai visitatori. Ogni volta che un visitatore trova una porta che può essere aperta, la apre sicuramente ed entra nella stanza (è anche possibile visitare la stessa stanza più volte). Per questo motivo, non vuoi alzare più del necessario i livelli di autenticazione sul tesserino dei visitatori. Tuttavia, per rendere il tour attraente, è necessario che nel tour si possano visitare in totale almeno $R$ stanze tra i $2$ uffici, incluse le stanze degli atri degli ascensori. Se abbassi troppo i livelli di autenticazione del tesserino, potrebbe non essere possibile soddisfare questa condizione.

L'azienda JOI ha $2$ uffici, e le stanze del $k$-esimo ufficio ($k = 1, 2$) sono disposte in $W_k$ stanze in direzione est-ovest e $H_k$ stanze in direzione nord-sud, per un totale di $W_k \times H_k$ stanze. Indicheremo con $(i, j)_k$ la $i$-esima stanza da ovest e $j$-esima da nord nel $k$-esimo ufficio.

Dati i valori di $W_k$, $H_k$ e $R$, la posizione dell'atrio degli ascensori $(X_k, Y_k)_k$ e il livello di riservatezza di ciascuna stanza, scrivi un programma per trovare il valore minimo possibile della somma dei livelli di autenticazione sul tesserino dei visitatori affinché i visitatori possano visitare almeno $R$ stanze in totale tra i $2$ uffici.

Per inciso, il modo in cui l'azienda JOI ottiene profitti realizzando «solo strane invenzioni» è un segreto di massima riservatezza anche all'interno dell'azienda, e nessuno lo conosce tranne il presidente.

Dati di input

• Nella $1$-a riga è scritto un intero positivo $R$ ($1 \le R \le 100000$).
• Dalla $2$-a riga in poi vengono forniti nell'ordine i dati dei $2$ uffici.
• I dati di ciascun ufficio sono forniti con gli interi positivi $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$) nella prima riga, seguiti da $H_k$ righe in cui l'$i$-esimo numero della $j$-esima riga è un intero $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) che rappresenta il livello di riservatezza della stanza $(i, j)_k$.
• Inoltre vale $R \le W_1 \times H_1 + W_2 \times H_2$.

Nei dati di test, per il $30\%$ del punteggio vale $R, W_k, H_k \le 100$.

Dati di output

Stampa $1$ sola riga contenente unicamente il valore minimo richiesto della somma dei livelli di autenticazione del tesserino.

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

Spiegazione degli esempi

Nell'Esempio 1, se si impostano i livelli di autenticazione del tesserino consegnato ai visitatori in modo che il livello di autenticazione per l'Ufficio $1$ sia $9$ e quello per l'Ufficio $2$ sia $6$, i visitatori possono visitare $5$ stanze (le stanze $(1, 1)_1, (1, 2)_1, (2, 1)_1$ dell'Ufficio $1$ e le stanze $(1, 1)_2, (2, 1)_2$ dell'Ufficio $2$). In questo caso, la somma dei livelli di autenticazione è $15$. Questo è il valore minimo della somma dei livelli di autenticazione per poter visitare in totale almeno $5$ stanze.

Nell'Esempio 3, se si impostano i livelli di autenticazione del tesserino consegnato ai visitatori in modo che il livello di autenticazione per l'Ufficio $1$ sia $9$ e quello per l'Ufficio $2$ sia $0$, i visitatori possono visitare $9$ stanze (le stanze $(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$ dell'Ufficio $1$). Non possono visitare nemmeno $1$ stanza dell'Ufficio $2$ (non possono nemmeno entrare nell'atrio degli ascensori $(1, 1)_2$). In questo caso, la somma dei livelli di autenticazione è $9$. Questo è il valore minimo della somma dei livelli di autenticazione per poter visitare in totale almeno $6$ stanze.