Verkefni

Þekkir þú fyrirtækið Just Odd Inventions? Starfsemi þessa fyrirtækis felst í því að gera „bara furðulegar uppfinningar (just odd inventions)“. Hér köllum við það til styttingar JOI-fyrirtækið.

JOI-fyrirtækið á $2$ skrifstofur og hvor skrifstofa um sig samanstendur af jafnstórum ferhyrningslaga herbergjum sem raðað er í rúðunet. Á milli allra herbergja sem eiga sameiginlega hlið er hurð búin auðkenningarbúnaði fyrir persónuskilríki. Þar sem JOI-fyrirtækið fer með trúnaðarupplýsingar af ýmsum stigum er jákvæð heiltala sem kallast trúnaðarstig sett fyrir hvert herbergi, og ekki er hægt að fara inn í herbergi nema hið óneikvæða heiltölu-auðkenningarstig sem tilgreint er á skilríkjunum fyrir þá skrifstofu sé stærra en eða jafnt og trúnaðarstig herbergisins. Eini inngangurinn og útgangurinn á hvorri skrifstofu er eina lyftuanddyrið, og trúnaðarstig herbergis lyftuanddyrisins er hið lægsta, sem er $1$. Þegar auðkenningarstigið fyrir þá skrifstofu er $0$ er ekki einu sinni hægt að fara inn í lyftuanddyrið.

Hjá JOI-fyrirtækinu var ákveðið, vegna skyndilegrar tillögu forstjórans, að halda skoðunarferð fyrir almenning til að skoða fyrirtækið að innan. Þú þarft að ákveða samsetningu auðkenningarstiganna á skilríkjunum sem afhent eru gestunum. Í hvert sinn sem gestur finnur hurð sem hægt er að opna, opnar hann hana alltaf og fer inn (einnig er hægt að heimsækja sama herbergið margoft). Vegna þessa viltu ekki hafa auðkenningarstigin á skilríkjum gestanna hærri en þörf krefur. Hins vegar, til að gera skoðunarferðina eftirsóknarverða, verður að vera hægt í ferðinni að heimsækja samtals að minnsta kosti $R$ herbergi á skrifstofunum $2$, að herbergjum lyftuanddyranna meðtöldum. Ef auðkenningarstigin á skilríkjunum eru stillt of lágt gæti verið ómögulegt að uppfylla þetta skilyrði.

JOI-fyrirtækið á $2$ skrifstofur, og herbergjunum á $k$-tu skrifstofunni ($k = 1, 2$) er raðað í $W_k$ herbergi í austur-vesturátt og $H_k$ herbergi í norður-suðurátt, alls $W_k \times H_k$ herbergi. Við táknum $i$-ta herbergið að vestan og $j$-ta herbergið að norðan á $k$-tu skrifstofunni með $(i, j)_k$.

Þegar gefin eru gildi $W_k$, $H_k$ og $R$, staðsetning lyftuanddyrisins $(X_k, Y_k)_k$ og trúnaðarstig hvers herbergis, skrifið forrit sem finnur minnsta mögulega gildið á summu auðkenningarstiga á skilríkjum gestsins þannig að gesturinn geti heimsótt samtals að minnsta kosti $R$ herbergi á skrifstofunum $2$.

Til gamans má geta þess að hvernig JOI-fyrirtækið hagnast á því að gera „bara furðulegar uppfinningar“ er algjört leyndarmál jafnvel innan fyrirtækisins, og enginn veit það nema forstjórinn.

Inntak

• Á $1$. línu er jákvæð heiltala $R$ ($1 \le R \le 100000$).
• Frá $2$. línu og áfram eru gögnin fyrir skrifstofurnar $2$ gefin í röð.
• Gögnin fyrir hvora skrifstofu eru gefin með jákvæðu heiltölunum $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$) á fyrstu línunni, og síðan fylgja $H_k$ línur þar sem $i$-ta talan á $j$-tu línunni er heiltala $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) sem táknar trúnaðarstig herbergis $(i, j)_k$.
• Ennfremur gildir $R \le W_1 \times H_1 + W_2 \times H_2$.

Úr prófunargögnunum gildir fyrir $30\%$ stiga að $R, W_k, H_k \le 100$.

Úttak

Prentið út $1$ línu sem inniheldur eingöngu hið umbeðna lágmarksgildi á summu auðkenningarstiga skilríkjanna.

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

Skýring á dæmum

Í Dæmi 1, ef auðkenningarstigin á skilríkjunum sem afhent eru gestinum eru stillt þannig að auðkenningarstigið fyrir Skrifstofu $1$ sé $9$ og auðkenningarstigið fyrir Skrifstofu $2$ sé $6$, getur gesturinn heimsótt $5$ herbergi (herbergin $(1, 1)_1, (1, 2)_1, (2, 1)_1$ á Skrifstofu $1$, og herbergin $(1, 1)_2, (2, 1)_2$ á Skrifstofu $2$). Þá er summa auðkenningarstiganna $15$. Þetta er lágmarksgildi summu auðkenningarstiga til að hægt sé að heimsækja samtals að minnsta kosti $5$ herbergi.

Í Dæmi 3, ef auðkenningarstigin á skilríkjunum sem afhent eru gestinum eru stillt þannig að auðkenningarstigið fyrir Skrifstofu $1$ sé $9$ og auðkenningarstigið fyrir Skrifstofu $2$ sé $0$, getur gesturinn heimsótt $9$ herbergi (herbergin $(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$ á Skrifstofu $1$). Ekki er hægt að heimsækja né $1$ herbergi á Skrifstofu $2$ (það er ekki einu sinni hægt að fara inn í lyftuanddyrið $(1, 1)_2$). Þá er summa auðkenningarstiganna $9$. Þetta er lágmarksgildi summu auðkenningarstiga til að hægt sé að heimsækja samtals að minnsta kosti $6$ herbergi.