Умова задачі

Чи знаєте ви компанію 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$ кімнат.