문제
당신은 Just Odd Inventions 사를 알고 있는가? 이 회사의 업무는 '그저 기묘한 발명(just odd inventions)'을 하는 것이다. 여기서는 줄여서 JOI 사라고 부른다.
JOI 사에는 $2$개의 사무소가 있으며, 각각 같은 크기의 정사각형 방이 바둑판 모양으로 늘어서서 이루어져 있다. 변을 맞대고 있는 모든 방 사이에는 신분증에 의한 인증 기능이 달린 문이 있다. JOI 사에서는 다양한 레벨의 기밀 정보를 다루고 있기 때문에, 방마다 기밀 레벨이라는 양의 정수가 설정되어 있으며, 신분증의 사무소마다 정해진 음이 아닌 정수의 인증 레벨이 기밀 레벨 이상이 아니면 그 방에 입실할 수 없다. 각 사무소의 출입구는 유일하게 존재하는 엘리베이터 홀뿐이며, 엘리베이터 홀이 있는 방의 기밀 레벨은 가장 낮은 $1$이다. 그 사무소에 대한 인증 레벨이 $0$일 때는 엘리베이터 홀에 들어가는 것조차 할 수 없다.
JOI 사에서는 사장의 돌발적인 제안으로 일반인에게 사내를 견학시켜 주는 투어를 실시하기로 했다. 당신은 견학자에게 건네줄 신분증의 인증 레벨 조합을 정해야 한다. 견학자는 열 수 있는 문을 발견하면 반드시 열고 안으로 들어간다(같은 방을 몇 번이고 방문하는 것도 가능하다). 그렇기 때문에 필요 이상으로 견학자의 신분증 인증 레벨을 높이고 싶지는 않다. 하지만 투어에 매력을 부여하기 위해, 투어에서는 엘리베이터 홀의 방을 포함해 $2$개의 사무소에서 합쳐서 $R$개 이상의 방을 방문할 수 있도록 해야 한다. 신분증의 인증 레벨을 너무 낮추면 이 조건을 만족시킬 수 없을지도 모른다.
JOI 사에는 사무소가 $2$개 있으며, 제$k$ 사무소 ($k = 1, 2$)의 방은 동서 방향으로 $W_k$개, 남북 방향으로 $H_k$개 늘어서 있어 전부 $W_k \times H_k$개 있다. 서쪽에서 $i$번째, 북쪽에서 $j$번째 방을 $(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$개의 줄 중 $j$번째 줄의 $i$번째에 방 $(i, j)_k$의 기밀 레벨을 나타내는 정수 $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$)로서 주어진다.
- 또한 $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 315Sample 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 64Sample 3
6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 79입출력 예제 설명
예제 1에서는 견학자에게 건네줄 신분증의 인증 레벨을 사무소 $1$의 인증 레벨이 $9$, 사무소 $2$의 인증 레벨이 $6$이 되도록 설정하면, 견학자는 $5$개의 방(사무소 $1$의 방 $(1, 1)_1, (1, 2)_1, (2, 1)_1$과 사무소 $2$의 방 $(1, 1)_2, (2, 1)_2$)을 방문할 수 있다. 이때 인증 레벨의 합은 $15$가 된다. 이것이 합계 $5$개 이상의 방을 방문할 수 있기 위한 인증 레벨 합의 최솟값이다.
예제 3에서는 견학자에게 건네줄 신분증의 인증 레벨을 사무소 $1$의 인증 레벨이 $9$, 사무소 $2$의 인증 레벨이 $0$이 되도록 설정하면, 견학자는 $9$개의 방(사무소 $1$의 방 $(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$)을 방문할 수 있다. 사무소 $2$의 방은 $1$개도 방문할 수 없다(엘리베이터 홀 $(1, 1)_2$에조차 들어갈 수 없다). 이때 인증 레벨의 합은 $9$가 된다. 이것이 합계 $6$개 이상의 방을 방문할 수 있기 위한 인증 레벨 합의 최솟값이다.
