Problem

Känner du till företaget Just Odd Inventions? Verksamheten i detta företag går ut på att göra ”bara udda uppfinningar (just odd inventions)”. Här kallar vi det kort för JOI-företaget.

JOI-företaget har $2$ kontor, och varje kontor består av kvadratiska rum av samma storlek ordnade i ett rutnät. Mellan alla rum som delar en sida finns en dörr utrustad med en autentiseringsfunktion med ID-kort. Eftersom JOI-företaget hanterar sekretessbelagd information på olika nivåer, har varje rum tilldelats ett positivt heltal som kallas sekretessnivå, och man kan inte gå in i ett rum om inte den icke-negativa heltalsbaserade autentiseringsnivån som anges på ID-kortet för det kontoret är större än eller lika med rummets sekretessnivå. Den enda in- och utgången på varje kontor är den enda hisshallen, och sekretessnivån för hisshallens rum är den lägsta, nämligen $1$. När autentiseringsnivån för kontoret är $0$ kan man inte ens gå in i hisshallen.

På JOI-företaget har man, efter ett plötsligt förslag från direktören, beslutat att anordna en rundtur där allmänheten får besöka företaget. Du måste bestämma kombinationen av autentiseringsnivåer på det ID-kort som delas ut till besökarna. Så fort en besökare hittar en dörr som går att öppna, öppnar besökaren den alltid och går in (det är också möjligt att besöka samma rum flera gånger). Därför vill du inte sätta autentiseringsnivåerna på besökarnas ID-kort högre än nödvändigt. Men för att göra rundturen attraktiv måste rundturen göra det möjligt att besöka sammanlagt minst $R$ rum på de $2$ kontoren, inklusive hisshallarnas rum. Om autentiseringsnivåerna på ID-kortet sätts för lågt kanske detta villkor inte kan uppfyllas.

JOI-företaget har $2$ kontor, och rummen på det $k$-te kontoret ($k = 1, 2$) är ordnade med $W_k$ rum i öst-västlig riktning och $H_k$ rum i nord-sydlig riktning, totalt $W_k \times H_k$ rum. Vi betecknar det $i$-te rummet från väster och $j$-te rummet från norr på det $k$-te kontoret med $(i, j)_k$.

Givet värdena på $W_k$, $H_k$ och $R$, hisshallens position $(X_k, Y_k)_k$ samt sekretessnivån för varje rum, skriv ett program som beräknar det minsta möjliga värdet på summan av autentiseringsnivåerna på besökarens ID-kort så att besökaren kan besöka sammanlagt minst $R$ rum på de $2$ kontoren.

För övrigt är det, hur JOI-företaget går med vinst genom att göra ”bara udda uppfinningar”, strängt hemligt till och med inom företaget, och ingen utom direktören vet det.

Indata

• På rad $1$ står ett positivt heltal $R$ ($1 \le R \le 100000$).
• Från och med rad $2$ ges datan för de $2$ kontoren i ordning.
• Datan för varje kontor består av de positiva heltalen $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örsta raden, följt av $H_k$ rader där det $i$-te talet på den $j$-te raden är ett heltal $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) som anger sekretessnivån för rum $(i, j)_k$.
• Dessutom gäller $R \le W_1 \times H_1 + W_2 \times H_2$.

Av testdatan gäller för $30\%$ av poängen att $R, W_k, H_k \le 100$.

Utdata

Skriv ut $1$ rad som enbart innehåller det sökta minsta värdet på summan av ID-kortets autentiseringsnivåer.

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

Förklaring av exempel

I Exempel 1, om autentiseringsnivåerna på ID-kortet som delas ut till besökaren ställs in så att autentiseringsnivån för Kontor $1$ är $9$ och autentiseringsnivån för Kontor $2$ är $6$, kan besökaren besöka $5$ rum (rummen $(1, 1)_1, (1, 2)_1, (2, 1)_1$ på Kontor $1$, samt rummen $(1, 1)_2, (2, 1)_2$ på Kontor $2$). Då blir summan av autentiseringsnivåerna $15$. Detta är det minsta värdet på summan av autentiseringsnivåer för att kunna besöka sammanlagt minst $5$ rum.

I Exempel 3, om autentiseringsnivåerna på ID-kortet som delas ut till besökaren ställs in så att autentiseringsnivån för Kontor $1$ är $9$ och autentiseringsnivån för Kontor $2$ är $0$, kan besökaren besöka $9$ rum (rummen $(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 inte ens $1$ rum besökas (man kan inte ens gå in i hisshallen $(1, 1)_2$). Då blir summan av autentiseringsnivåerna $9$. Detta är det minsta värdet på summan av autentiseringsnivåer för att kunna besöka sammanlagt minst $6$ rum.