Aufgabenstellung

Kennen Sie die Firma Just Odd Inventions? Die Tätigkeit dieser Firma besteht darin, „einfach seltsame Erfindungen (just odd inventions)“ zu machen. Hier nennen wir sie kurz die JOI-Firma.

Die JOI-Firma besitzt $2$ Büros, die jeweils aus gleich großen quadratischen Räumen bestehen, die gitterförmig angeordnet sind. Zwischen allen Räumen, die eine gemeinsame Kante haben, befindet sich eine Tür mit einer Ausweis-Authentifizierungsfunktion. Da die JOI-Firma vertrauliche Informationen verschiedener Stufen verarbeitet, ist für jeden Raum eine positive ganze Zahl namens Geheimhaltungsstufe festgelegt, und man kann einen Raum nur betreten, wenn die auf dem Ausweis für das jeweilige Büro festgelegte nichtnegative ganzzahlige Authentifizierungsstufe mindestens so groß wie die Geheimhaltungsstufe des Raums ist. Der einzige Ein- und Ausgang jedes Büros ist die einzige Aufzugshalle, und die Geheimhaltungsstufe des Raums der Aufzugshalle hat den niedrigsten Wert $1$. Wenn die Authentifizierungsstufe für dieses Büro $0$ beträgt, kann man nicht einmal die Aufzugshalle betreten.

In der JOI-Firma wurde aufgrund eines spontanen Vorschlags des Präsidenten beschlossen, eine Führung zu veranstalten, bei der die breite Öffentlichkeit das Firmeninnere besichtigen kann. Sie müssen die Kombination der Authentifizierungsstufen auf dem Ausweis festlegen, der den Besuchern ausgehändigt wird. Sobald ein Besucher eine Tür findet, die sich öffnen lässt, öffnet er sie garantiert und geht hinein (derselbe Raum kann auch mehrmals besucht werden). Daher möchten Sie die Authentifizierungsstufen auf dem Ausweis der Besucher nicht unnötig hoch einstellen. Um die Führung jedoch attraktiv zu gestalten, muss es bei der Führung möglich sein, einschließlich der Räume der Aufzugshallen in den $2$ Büros zusammen mindestens $R$ Räume zu besuchen. Wenn Sie die Authentifizierungsstufen auf dem Ausweis zu niedrig ansetzen, kann diese Bedingung möglicherweise nicht erfüllt werden.

Die JOI-Firma hat $2$ Büros, und im $k$-ten Büro ($k = 1, 2$) sind in Ost-West-Richtung $W_k$ Räume und in Nord-Süd-Richtung $H_k$ Räume angeordnet, insgesamt also $W_k \times H_k$ Räume. Wir bezeichnen den $i$-ten Raum von Westen und $j$-ten Raum von Norden im $k$-ten Büro mit $(i, j)_k$.

Gegeben sind die Werte von $W_k$, $H_k$ und $R$, die Position der Aufzugshalle $(X_k, Y_k)_k$ sowie die Geheimhaltungsstufe jedes Raums. Schreiben Sie ein Programm, das das Minimum der Summe der Authentifizierungsstufen auf dem Ausweis der Besucher berechnet, sodass die Besucher in den $2$ Büros zusammen mindestens $R$ Räume besuchen können.

Übrigens ist es selbst innerhalb der Firma streng geheim, wie die JOI-Firma mit „einfach seltsamen Erfindungen“ Gewinn erzielt, und außer dem Präsidenten weiß es niemand.

Eingabe

• In der $1$. Zeile steht eine positive ganze Zahl $R$ ($1 \le R \le 100000$).
• Ab der $2$. Zeile folgen nacheinander die Daten der $2$ Büros.
• Die Daten eines Büros bestehen in der ersten Zeile aus den positiven ganzen Zahlen $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$), gefolgt von $H_k$ Zeilen, wobei in der $j$-ten Zeile an $i$-ter Stelle die ganze Zahl $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) steht, die die Geheimhaltungsstufe des Raums $(i, j)_k$ angibt.
• Zudem gilt $R \le W_1 \times H_1 + W_2 \times H_2$.

Bei den Testdaten gilt für $30\%$ der Punkte $R, W_k, H_k \le 100$.

Ausgabe

Geben Sie $1$ Zeile aus, die nur das gesuchte Minimum der Summe der Authentifizierungsstufen des Ausweises enthält.

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

Erläuterung der Beispiele

Wenn in Beispiel 1 die Authentifizierungsstufen des den Besuchern ausgehändigten Ausweises so eingestellt werden, dass die Authentifizierungsstufe für Büro $1$ gleich $9$ und die für Büro $2$ gleich $6$ ist, können die Besucher $5$ Räume besuchen (die Räume $(1, 1)_1, (1, 2)_1, (2, 1)_1$ in Büro $1$ sowie die Räume $(1, 1)_2, (2, 1)_2$ in Büro $2$). In diesem Fall beträgt die Summe der Authentifizierungsstufen $15$. Dies ist das Minimum der Summe der Authentifizierungsstufen, um insgesamt mindestens $5$ Räume besuchen zu können.

Wenn in Beispiel 3 die Authentifizierungsstufen des den Besuchern ausgehändigten Ausweises so eingestellt werden, dass die Authentifizierungsstufe für Büro $1$ gleich $9$ und die für Büro $2$ gleich $0$ ist, können die Besucher $9$ Räume besuchen (die Räume $(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$ in Büro $1$). In Büro $2$ kann kein einziger ($1$) Raum besucht werden (nicht einmal die Aufzugshalle $(1, 1)_2$ kann betreten werden). In diesem Fall beträgt die Summe der Authentifizierungsstufen $9$. Dies ist das Minimum der Summe der Authentifizierungsstufen, um insgesamt mindestens $6$ Räume besuchen zu können.