Authentication Level

A company has two offices. Each office is a grid of equally sized square rooms, and every pair of rooms that share an edge is connected by a door protected by an ID-card check.

Each room has a positive integer security level. An ID card is assigned a non-negative integer authentication level for each office; a visitor may enter a room only if that office's authentication level is at least the room's security level.

The only entrance to each office is a single elevator hall. The security level of the elevator hall is the smallest possible value, $1$. If the authentication level for an office is $0$, the visitor cannot even enter that office's elevator hall.

Whenever a visitor can open a door, they always open it and go through (rooms may be visited more than once). Therefore, once the authentication levels are fixed, the visitor reaches exactly those rooms that are connected to the elevator hall through rooms whose security level does not exceed that office's authentication level.

You must set the card's authentication levels so that, across both offices, the visitor can visit at least $R$ rooms in total (counting the elevator halls). Find the minimum possible sum of the two authentication levels.

Office $k$ ($k = 1, 2$) has $W_k$ rooms in the west-east direction and $H_k$ rooms in the north-south direction, for $W_k \times H_k$ rooms in total. The room that is $i$-th from the west and $j$-th from the north is denoted $(i, j)_k$.

The first line contains the integer $R$ ($1 \le R \le 100000$).

The data of the two offices then follow in order. The data of office $k$ begins with a line containing four integers $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$), where $(X_k, Y_k)$ is the position of the elevator hall. The next $H_k$ lines follow; the $j$-th of them contains $W_k$ integers, the $i$-th of which is $L_{k,i,j}$ ($1 \le L_{k,i,j} < 10^8$), the security level of room $(i, j)_k$.

It is also guaranteed that $R \le W_1 \times H_1 + W_2 \times H_2$.

Print, on a single line, the minimum possible sum of the two authentication levels.