Énoncé

Connaissez-vous l'entreprise Just Odd Inventions ? L'activité de cette entreprise consiste à faire « juste d'étranges inventions (just odd inventions) ». Ici, nous l'appellerons simplement l'entreprise JOI.

L'entreprise JOI possède $2$ bureaux, et chacun est formé de salles carrées de même taille disposées en grille. Entre toutes les paires de salles adjacentes par un côté se trouve une porte équipée d'une fonction d'authentification par badge d'identité. Comme l'entreprise JOI traite des informations confidentielles de différents niveaux, un entier strictement positif appelé niveau de confidentialité est défini pour chaque salle, et l'on ne peut entrer dans une salle que si le niveau d'authentification (un entier positif ou nul défini sur le badge pour ce bureau) est supérieur ou égal au niveau de confidentialité de la salle. La seule entrée/sortie de chaque bureau est l'unique hall d'ascenseur, et le niveau de confidentialité de la salle du hall d'ascenseur est le plus bas, à savoir $1$. Lorsque le niveau d'authentification pour ce bureau vaut $0$, on ne peut même pas entrer dans le hall d'ascenseur.

Dans l'entreprise JOI, suite à une proposition soudaine du président, il a été décidé d'organiser une visite guidée permettant au grand public de visiter les locaux de l'entreprise. Vous devez choisir la combinaison des niveaux d'authentification du badge remis aux visiteurs. Dès qu'un visiteur trouve une porte qu'il peut ouvrir, il l'ouvre systématiquement et entre dans la salle (il est également possible de visiter plusieurs fois la même salle). Pour cette raison, vous ne souhaitez pas fixer les niveaux d'authentification du badge des visiteurs plus haut que nécessaire. Cependant, pour rendre la visite attrayante, il faut que les visiteurs puissent visiter au total au moins $R$ salles sur l'ensemble des $2$ bureaux, y compris les salles des halls d'ascenseur. Si vous fixez les niveaux d'authentification du badge trop bas, cette condition risque de ne pas pouvoir être remplie.

L'entreprise JOI possède $2$ bureaux, et les salles du $k$-e bureau ($k = 1, 2$) sont disposées à raison de $W_k$ salles dans la direction est-ouest et $H_k$ salles dans la direction nord-sud, soit $W_k \times H_k$ salles au total. Nous noterons $(i, j)_k$ la $i$-e salle depuis l'ouest et $j$-e salle depuis le nord dans le $k$-e bureau.

Étant donné les valeurs de $W_k$, $H_k$ et $R$, les positions des halls d'ascenseur $(X_k, Y_k)_k$ ainsi que le niveau de confidentialité de chaque salle, écrivez un programme qui détermine la valeur minimale possible de la somme des niveaux d'authentification du badge des visiteurs permettant aux visiteurs de visiter au total au moins $R$ salles sur l'ensemble des $2$ bureaux.

Soit dit en passant, la manière dont l'entreprise JOI réalise des bénéfices en faisant « juste d'étranges inventions » est un secret absolu même au sein de l'entreprise, et personne d'autre que le président ne le sait.

Entrée

• La $1$-re ligne contient un entier strictement positif $R$ ($1 \le R \le 100000$).
• À partir de la $2$-e ligne, les données des $2$ bureaux sont fournies dans l'ordre.
• Les données d'un bureau comportent sur la première ligne les entiers strictement positifs $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$), suivis de $H_k$ lignes où le $i$-e nombre de la $j$-e ligne est un entier $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) représentant le niveau de confidentialité de la salle $(i, j)_k$.
• De plus, $R \le W_1 \times H_1 + W_2 \times H_2$ est vérifié.

Parmi les données de test, pour $30\%$ des points, $R, W_k, H_k \le 100$ sont vérifiés.

Sortie

Affichez $1$ seule ligne contenant uniquement la valeur minimale recherchée de la somme des niveaux d'authentification du badge.

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

Explication des exemples

Dans l'exemple 1, si l'on configure les niveaux d'authentification du badge remis aux visiteurs de sorte que le niveau d'authentification du Bureau $1$ soit $9$ et celui du Bureau $2$ soit $6$, les visiteurs peuvent visiter $5$ salles (les salles $(1, 1)_1, (1, 2)_1, (2, 1)_1$ du Bureau $1$, et les salles $(1, 1)_2, (2, 1)_2$ du Bureau $2$). La somme des niveaux d'authentification vaut alors $15$. C'est la somme minimale des niveaux d'authentification permettant de visiter au moins $5$ salles au total.

Dans l'exemple 3, si l'on configure les niveaux d'authentification du badge remis aux visiteurs de sorte que le niveau d'authentification du Bureau $1$ soit $9$ et celui du Bureau $2$ soit $0$, les visiteurs peuvent visiter $9$ salles (les salles $(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$ du Bureau $1$). Ils ne peuvent visiter pas même $1$ salle du Bureau $2$ (ils ne peuvent même pas entrer dans le hall d'ascenseur $(1, 1)_2$). La somme des niveaux d'authentification vaut alors $9$. C'est la somme minimale des niveaux d'authentification permettant de visiter au moins $6$ salles au total.