Условие задачи

Знаете ли вы компанию Just Odd Inventions? Деятельность этой компании заключается в создании «просто странных изобретений (just odd inventions)». Здесь мы для краткости будем называть её компанией JOI.

У компании JOI есть $2$ офиса, каждый из которых состоит из одинаковых по размеру квадратных комнат, расположенных в виде сетки. Между каждыми двумя комнатами, имеющими общую сторону, есть дверь, оснащённая функцией авторизации по удостоверению личности. Поскольку компания JOI работает с секретной информацией разного уровня, для каждой комнаты задано положительное целое число, называемое уровнем секретности, и войти в комнату можно только в том случае, если неотрицательный целый уровень авторизации, установленный на удостоверении для данного офиса, не меньше уровня секретности этой комнаты. Единственным входом и выходом каждого офиса является единственный лифтовый холл, а уровень секретности комнаты лифтового холла — самый низкий, равный $1$. Если уровень авторизации для этого офиса равен $0$, то нельзя войти даже в лифтовый холл.

В компании JOI по внезапному предложению президента решено было провести экскурсию для широкой публики с осмотром помещений компании. Вам нужно выбрать комбинацию уровней авторизации на удостоверении, выдаваемом посетителям. Если посетитель находит дверь, которую можно открыть, он обязательно открывает её и входит внутрь (посещать одну и ту же комнату можно сколько угодно раз). Поэтому вы не хотите делать уровень авторизации на удостоверении посетителей выше, чем это необходимо. Однако, чтобы сделать экскурсию привлекательной, нужно, чтобы во время экскурсии посетители могли посетить в общей сложности не менее $R$ комнат в $2$ офисах, включая комнаты лифтовых холлов. Если сделать уровень авторизации на удостоверении слишком низким, это условие может оказаться невыполнимым.

В компании JOI $2$ офиса, и комнаты $k$-го офиса ($k = 1, 2$) расположены по $W_k$ комнат в направлении восток-запад и по $H_k$ комнат в направлении север-юг, всего $W_k \times H_k$ комнат. Будем обозначать $i$-ю комнату с запада и $j$-ю с севера в $k$-м офисе через $(i, j)_k$.

По заданным значениям $W_k$, $H_k$ и $R$, положению лифтового холла $(X_k, Y_k)_k$ и уровням секретности каждой комнаты напишите программу, которая находит минимальное возможное значение суммы уровней авторизации на удостоверении посетителя, позволяющее посетителю посетить в $2$ офисах суммарно не менее $R$ комнат.

К слову, то, каким образом компания JOI получает прибыль, делая «просто странные изобретения», является строжайшей тайной даже внутри компании, и кроме президента об этом никто не знает.

Входные данные

• В $1$-й строке записано положительное целое число $R$ ($1 \le R \le 100000$).
• Со $2$-й строки последовательно задаются данные для $2$ офисов.
• Данные каждого офиса задаются положительными целыми числами $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$) в первой строке, за которыми следуют $H_k$ строк, где $i$-е число в $j$-й строке — целое число $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$), обозначающее уровень секретности комнаты $(i, j)_k$.
• Кроме того, выполняется $R \le W_1 \times H_1 + W_2 \times H_2$.

В тестовых данных на $30\%$ баллов выполняется $R, W_k, H_k \le 100$.

Выходные данные

Выведите $1$ строку, содержащую только искомое минимальное значение суммы уровней авторизации удостоверения.

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

Пояснение к примерам

В Примере 1, если установить уровни авторизации выдаваемого посетителю удостоверения так, чтобы уровень авторизации для Офиса $1$ был равен $9$, а для Офиса $2$ был равен $6$, то посетитель сможет посетить $5$ комнат (комнаты $(1, 1)_1, (1, 2)_1, (2, 1)_1$ Офиса $1$ и комнаты $(1, 1)_2, (2, 1)_2$ Офиса $2$). При этом сумма уровней авторизации равна $15$. Это минимальное значение суммы уровней авторизации, необходимое для того, чтобы можно было посетить суммарно не менее $5$ комнат.

В Примере 3, если установить уровни авторизации выдаваемого посетителю удостоверения так, чтобы уровень авторизации для Офиса $1$ был равен $9$, а для Офиса $2$ был равен $0$, то посетитель сможет посетить $9$ комнат (комнаты $(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$ Офиса $1$). В Офисе $2$ нельзя посетить ни $1$ комнаты (нельзя даже войти в лифтовый холл $(1, 1)_2$). При этом сумма уровней авторизации равна $9$. Это минимальное значение суммы уровней авторизации, необходимое для того, чтобы можно было посетить суммарно не менее $6$ комнат.