Oppgave

Kjenner du til selskapet Just Odd Inventions? Virksomheten til dette selskapet går ut på å lage «bare rare oppfinnelser (just odd inventions)». Her kaller vi det kort for JOI-selskapet.

JOI-selskapet har $2$ kontorer, og hvert kontor består av kvadratiske rom av samme størrelse stilt opp i et rutenett. Mellom alle rom som deler en kant, er det en dør utstyrt med en autentiseringsfunksjon med ID-kort. Siden JOI-selskapet håndterer konfidensiell informasjon på ulike nivåer, er det satt et positivt heltall kalt sikkerhetsnivå for hvert rom, og man kan ikke gå inn i et rom med mindre det ikke-negative heltallsbaserte autentiseringsnivået som er angitt på ID-kortet for det kontoret, er større enn eller lik rommets sikkerhetsnivå. Den eneste inngangen/utgangen på hvert kontor er den ene heishallen, og sikkerhetsnivået til heishallrommet er det laveste, nemlig $1$. Når autentiseringsnivået for dette kontoret er $0$, kan man ikke engang gå inn i heishallen.

I JOI-selskapet ble det, etter et plutselig forslag fra direktøren, bestemt å arrangere en omvisning der folk flest får besøke innsiden av selskapet. Du må bestemme kombinasjonen av autentiseringsnivåer på ID-kortet som deles ut til de besøkende. Så snart en besøkende finner en dør som kan åpnes, vil vedkommende alltid åpne den og gå inn (det er også mulig å besøke det samme rommet flere ganger). Derfor ønsker du ikke å sette autentiseringsnivåene på de besøkendes ID-kort høyere enn nødvendig. Men for å gjøre omvisningen attraktiv, må omvisningen gjøre det mulig å besøke til sammen minst $R$ rom på de $2$ kontorene, inkludert heishallrommene. Hvis autentiseringsnivåene på ID-kortet settes for lavt, er det ikke sikkert at dette kravet kan oppfylles.

JOI-selskapet har $2$ kontorer, og rommene på det $k$-te kontoret ($k = 1, 2$) er stilt opp med $W_k$ rom i øst-vest-retning og $H_k$ rom i nord-sør-retning, totalt $W_k \times H_k$ rom. Vi betegner det $i$-te rommet fra vest og $j$-te rommet fra nord på det $k$-te kontoret med $(i, j)_k$.

Gitt verdiene til $W_k$, $H_k$ og $R$, posisjonen til heishallen $(X_k, Y_k)_k$ samt sikkerhetsnivået til hvert rom, skriv et program som finner den minste mulige verdien av summen av autentiseringsnivåene på den besøkendes ID-kort, slik at den besøkende kan besøke til sammen minst $R$ rom på de $2$ kontorene.

For øvrig er det hvordan JOI-selskapet tjener penger på å lage «bare rare oppfinnelser» strengt hemmelig selv internt i selskapet, og ingen andre enn direktøren vet det.

Inndata

• På linje $1$ står et positivt heltall $R$ ($1 \le R \le 100000$).
• Fra og med linje $2$ oppgis dataene for de $2$ kontorene i rekkefølge.
• Dataene for hvert kontor består av de positive heltallene $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$) på første linje, etterfulgt av $H_k$ linjer der det $i$-te tallet på den $j$-te linjen er et heltall $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) som angir sikkerhetsnivået til rom $(i, j)_k$.
• Videre gjelder $R \le W_1 \times H_1 + W_2 \times H_2$.

Av testdataene gjelder det for $30\%$ av poengene at $R, W_k, H_k \le 100$.

Utdata

Skriv ut $1$ linje som kun inneholder den søkte minste verdien av summen av autentiseringsnivåene på ID-kortet.

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

Forklaring av eksempler

I Eksempel 1, hvis autentiseringsnivåene på ID-kortet som deles ut til den besøkende, settes slik at autentiseringsnivået for Kontor $1$ er $9$ og autentiseringsnivået for Kontor $2$ er $6$, kan den besøkende besøke $5$ rom (rommene $(1, 1)_1, (1, 2)_1, (2, 1)_1$ på Kontor $1$ og rommene $(1, 1)_2, (2, 1)_2$ på Kontor $2$). Da blir summen av autentiseringsnivåene $15$. Dette er den minste verdien av summen av autentiseringsnivåer for å kunne besøke til sammen minst $5$ rom.

I Eksempel 3, hvis autentiseringsnivåene på ID-kortet som deles ut til den besøkende, settes slik at autentiseringsnivået for Kontor $1$ er $9$ og autentiseringsnivået for Kontor $2$ er $0$, kan den besøkende besøke $9$ rom (rommene $(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$ på Kontor $1$). På Kontor $2$ kan ikke engang $1$ rom besøkes (man kan ikke engang gå inn i heishallen $(1, 1)_2$). Da blir summen av autentiseringsnivåene $9$. Dette er den minste verdien av summen av autentiseringsnivåer for å kunne besøke til sammen minst $6$ rom.