Treść zadania

Czy znasz firmę Just Odd Inventions? Działalność tej firmy polega na tworzeniu „po prostu dziwnych wynalazków (just odd inventions)”. Tutaj w skrócie będziemy nazywać ją firmą JOI.

Firma JOI posiada $2$ biura, a każde z nich składa się z kwadratowych pokoi tej samej wielkości ułożonych w siatkę. Pomiędzy każdą parą pokoi stykających się bokiem znajdują się drzwi wyposażone w funkcję uwierzytelniania za pomocą identyfikatora. Ponieważ firma JOI przetwarza informacje poufne o różnych poziomach, dla każdego pokoju określona jest dodatnia liczba całkowita nazywana poziomem poufności, i nie można wejść do pokoju, jeśli określony na identyfikatorze dla danego biura nieujemny całkowity poziom uwierzytelnienia nie jest większy lub równy poziomowi poufności tego pokoju. Jedynym wejściem i wyjściem w każdym biurze jest jedyny hol windowy, a poziom poufności pokoju holu windowego jest najniższy i wynosi $1$. Gdy poziom uwierzytelnienia dla danego biura wynosi $0$, nie można nawet wejść do holu windowego.

W firmie JOI, w wyniku nagłej propozycji prezesa, postanowiono zorganizować wycieczkę umożliwiającą zwykłym ludziom zwiedzenie wnętrza firmy. Musisz ustalić kombinację poziomów uwierzytelnienia na identyfikatorze wręczanym zwiedzającym. Gdy zwiedzający znajdzie drzwi, które da się otworzyć, zawsze je otwiera i wchodzi do środka (możliwe jest również wielokrotne odwiedzanie tego samego pokoju). Z tego powodu nie chcesz ustawiać poziomów uwierzytelnienia na identyfikatorze zwiedzających wyżej niż to konieczne. Aby jednak wycieczka była atrakcyjna, podczas wycieczki zwiedzający muszą mieć możliwość odwiedzenia łącznie co najmniej $R$ pokoi w $2$ biurach, wliczając w to pokoje holi windowych. Jeśli poziomy uwierzytelnienia na identyfikatorze zostaną ustawione zbyt nisko, spełnienie tego warunku może okazać się niemożliwe.

Firma JOI posiada $2$ biura, a pokoje w $k$-tym biurze ($k = 1, 2$) są ułożone po $W_k$ pokoi w kierunku wschód-zachód oraz $H_k$ pokoi w kierunku północ-południe, co daje łącznie $W_k \times H_k$ pokoi. Pokój $i$-ty od zachodu i $j$-ty od północy w $k$-tym biurze oznaczamy przez $(i, j)_k$.

Mając dane wartości $W_k$, $H_k$ oraz $R$, pozycje holi windowych $(X_k, Y_k)_k$, a także poziomy poufności poszczególnych pokoi, napisz program, który wyznaczy minimalną możliwą sumę poziomów uwierzytelnienia na identyfikatorze zwiedzającego, tak aby zwiedzający mógł odwiedzić łącznie co najmniej $R$ pokoi w $2$ biurach.

Nawiasem mówiąc, to, w jaki sposób firma JOI czerpie zyski z tworzenia „po prostu dziwnych wynalazków”, jest ściśle tajne nawet wewnątrz firmy i poza prezesem nikt tego nie wie.

Wejście

• W $1$-szym wierszu znajduje się dodatnia liczba całkowita $R$ ($1 \le R \le 100000$).
• Od $2$-giego wiersza podawane są kolejno dane dla $2$ biur.
• Dane dla każdego biura składają się z dodatnich liczb całkowitych $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$) w pierwszym wierszu, po których następuje $H_k$ wierszy, gdzie $i$-ta liczba w $j$-tym wierszu jest liczbą całkowitą $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) oznaczającą poziom poufności pokoju $(i, j)_k$.
• Ponadto zachodzi $R \le W_1 \times H_1 + W_2 \times H_2$.

Wśród danych testowych, dla $30\%$ punktów zachodzi $R, W_k, H_k \le 100$.

Wyjście

Wypisz $1$ wiersz zawierający wyłącznie szukaną minimalną wartość sumy poziomów uwierzytelnienia na identyfikatorze.

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

Wyjaśnienie przykładów

W Przykładzie 1, jeśli poziomy uwierzytelnienia na identyfikatorze wręczanym zwiedzającemu zostaną ustawione tak, że poziom uwierzytelnienia dla Biura $1$ wynosi $9$, a dla Biura $2$ wynosi $6$, zwiedzający może odwiedzić $5$ pokoi (pokoje $(1, 1)_1, (1, 2)_1, (2, 1)_1$ w Biurze $1$ oraz pokoje $(1, 1)_2, (2, 1)_2$ w Biurze $2$). Wówczas suma poziomów uwierzytelnienia wynosi $15$. Jest to minimalna wartość sumy poziomów uwierzytelnienia pozwalająca odwiedzić łącznie co najmniej $5$ pokoi.

W Przykładzie 3, jeśli poziomy uwierzytelnienia na identyfikatorze wręczanym zwiedzającemu zostaną ustawione tak, że poziom uwierzytelnienia dla Biura $1$ wynosi $9$, a dla Biura $2$ wynosi $0$, zwiedzający może odwiedzić $9$ pokoi (pokoje $(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$ w Biurze $1$). W Biurze $2$ nie może odwiedzić ani $1$ pokoju (nie może nawet wejść do holu windowego $(1, 1)_2$). Wówczas suma poziomów uwierzytelnienia wynosi $9$. Jest to minimalna wartość sumy poziomów uwierzytelnienia pozwalająca odwiedzić łącznie co najmniej $6$ pokoi.