Tehtävänanto

Tunnetko Just Odd Inventions -yrityksen? Tämän yrityksen toimialana on tehdä ”vain outoja keksintöjä (just odd inventions)”. Tässä kutsumme sitä lyhyesti JOI-yhtiöksi.

JOI-yhtiöllä on $2$ toimistoa, joista kumpikin koostuu ruudukoksi järjestetyistä samankokoisista neliönmuotoisista huoneista. Kaikkien sivustaan vierekkäisten huoneiden välissä on henkilökorttitodennuksella varustettu ovi. Koska JOI-yhtiössä käsitellään eritasoisia salaisia tietoja, jokaiselle huoneelle on määritetty positiivinen kokonaisluku, jota kutsutaan turvaluokitukseksi, eikä huoneeseen pääse sisään, ellei henkilökorttiin kyseiselle toimistolle määritetty epänegatiivinen kokonaislukuarvoinen todennustaso ole vähintään yhtä suuri kuin huoneen turvaluokitus. Kummankin toimiston ainoa sisään- ja uloskäynti on sen ainoa hissiaula, ja hissiaulan huoneen turvaluokitus on matalin mahdollinen eli $1$. Kun kyseisen toimiston todennustaso on $0$, edes hissiaulaan ei pääse sisään.

JOI-yhtiössä päätettiin toimitusjohtajan äkillisestä ehdotuksesta järjestää kierros, jolla tavalliset ihmiset pääsevät tutustumaan yhtiön tiloihin. Sinun on päätettävä vierailijoille annettavan henkilökortin todennustasojen yhdistelmä. Aina kun vierailija löytää oven, jonka voi avata, hän varmasti avaa sen ja astuu sisään (samassa huoneessa voi myös käydä useita kertoja). Tämän vuoksi et halua asettaa vierailijan henkilökortin todennustasoja tarpeettoman korkeiksi. Jotta kierros olisi kuitenkin houkutteleva, kierroksella on voitava vierailla hissiaulojen huoneet mukaan lukien yhteensä vähintään $R$ huoneessa $2$ toimistossa yhteensä. Jos henkilökortin todennustasot asetetaan liian mataliksi, tätä ehtoa ei ehkä voida täyttää.

JOI-yhtiöllä on $2$ toimistoa, ja $k$-nnen toimiston ($k = 1, 2$) huoneet on järjestetty siten, että itä-länsisuunnassa on $W_k$ huonetta ja pohjois-eteläsuunnassa $H_k$ huonetta, eli yhteensä $W_k \times H_k$ huonetta. Merkitään lännestä lukien $i$-ttä ja pohjoisesta lukien $j$-ttä huonetta $k$-nnessa toimistossa merkinnällä $(i, j)_k$.

Kun annetaan lukujen $W_k$, $H_k$ ja $R$ arvot, hissiaulan sijainti $(X_k, Y_k)_k$ sekä kunkin huoneen turvaluokitus, kirjoita ohjelma, joka etsii vierailijan henkilökortin todennustasojen summan pienimmän mahdollisen arvon, jolla vierailija voi käydä $2$ toimistossa yhteensä vähintään $R$ huoneessa.

Muuten, se miten JOI-yhtiö tekee voittoa tekemällä ”vain outoja keksintöjä”, on yhtiön sisälläkin huippusalaista, eikä sitä tiedä kukaan muu kuin toimitusjohtaja.

Syöte

• Rivillä $1$ on positiivinen kokonaisluku $R$ ($1 \le R \le 100000$).
• Riviltä $2$ alkaen annetaan järjestyksessä $2$ toimiston tiedot.
• Toimiston tiedoissa on ensimmäisellä rivillä positiiviset kokonaisluvut $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$), ja niitä seuraavilla $H_k$ rivillä $j$-nnen rivin $i$-ntenä lukuna on huoneen $(i, j)_k$ turvaluokitusta kuvaava kokonaisluku $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$).
• Lisäksi pätee $R \le W_1 \times H_1 + W_2 \times H_2$.

Testiaineistosta $30\%$ pisteistä täyttää ehdon $R, W_k, H_k \le 100$.

Tuloste

Tulosta $1$ rivi, joka sisältää vain haetun henkilökortin todennustasojen summan pienimmän mahdollisen arvon.

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

Esimerkkien selitys

Esimerkissä 1, jos vierailijalle annettavan henkilökortin todennustasot asetetaan siten, että toimiston $1$ todennustaso on $9$ ja toimiston $2$ todennustaso on $6$, vierailija voi käydä $5$ huoneessa (toimiston $1$ huoneissa $(1, 1)_1, (1, 2)_1, (2, 1)_1$ sekä toimiston $2$ huoneissa $(1, 1)_2, (2, 1)_2$). Tällöin todennustasojen summa on $15$. Tämä on pienin mahdollinen todennustasojen summa, jolla voidaan käydä yhteensä vähintään $5$ huoneessa.

Esimerkissä 3, jos vierailijalle annettavan henkilökortin todennustasot asetetaan siten, että toimiston $1$ todennustaso on $9$ ja toimiston $2$ todennustaso on $0$, vierailija voi käydä $9$ huoneessa (toimiston $1$ huoneissa $(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$). Toimiston $2$ huoneista ei voida käydä edes $1$ huoneessa (edes hissiaulaan $(1, 1)_2$ ei pääse sisään). Tällöin todennustasojen summa on $9$. Tämä on pienin mahdollinen todennustasojen summa, jolla voidaan käydä yhteensä vähintään $6$ huoneessa.