Problem : 10 - 電腦教室！

Problem Statistics

Solved Member: 39　　Submission: 108　　User Tried: 41

Statement:

一天，一如往常的你來到學校的電腦教室聽好威hanhan上課。癥結的是，你發現電腦教室全被鎖起來了，所以你必須想辦法解鎖，這樣hanhan才有辦法繼續講課QAQ。
附中的電腦教室如你所知，分成二樓和三樓兩層樓，每層樓各有兩間電腦教室。但是由於現在是暑假所以只有二樓的兩間電腦教室有開而已，兩間電腦教室的電腦排列為$W_1 \times H_1$和$W_2 \times H_2$的長方形。

以下是一些打開電腦的小規定：
1.打開電腦的方法是插入奇怪的USB，只要這個USB權限大於或等於這台電腦所需要的權限就可以解鎖。
2.現在有2個USB，你跟hanhan各拿一個在不同的電腦教室。
3.hanhan跟你正好站在兩間電腦教室的($x_1$,$y_1$)及($x_2$,$y_2$)，這兩台電腦的權限為1，你們決定從這兩台電腦先開鎖。
4.每間電腦教室講師希望上課的人能坐在一起，這樣比較好討論。所謂坐在一起的意思是前後左右至少存在一台已經開鎖的電腦，如果這間教室只有一個人的話就只能夠選第一台電腦。

現在有N個人要上課，你想計算兩個USB最少的權限和為多少才能打開至少N台電腦？

Input:Output:

每個輸入檔只有一筆測資。
第一行有個正整數N($1 \leq N \leq 100000$)，代表想要來上課的人數。
第二行為四個正整數$W_1$,$H_1$,$x_1$,$y_1$，代表第一間電腦教室為$W_1 \times H_1$的大小，hanhan決定從($x_1$,$y_1$)開始開鎖。
接下來$H_1$行，每行有$W_1$個正整數，第j行第i個數字代表開啟第一間電腦教室位置(i,j)電腦鎖需要的權限。
下一行輸入$W_2$,$H_2$,$x_2$,$y_2$，代表第二間電腦教室為$W_2 \times H_2$的大小，你決定從($x_2$,$y_2$)這台電腦開始開鎖。
接下來$H_2$行，每行有$W_2$個正整數，第j行第i個數字代表開啟第二間電腦教室位置(i,j)電腦鎖需要的權限。

輸出兩個USB總和最小的數字。

Sample Input:Sample Output:

1：
5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3

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

3:
6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 7

1：
15

2：
4

3：
9

HINT:

$1 \leq N \leq 100000$
$1 \leq x_i \leq W_i \leq 500$
$1 \leq y_i \leq H_i \leq 500$
1 <= 開啟任一台電腦所需權限 <= 10^8
$N \leq W_1 \times H_1 + W_2 \times H_2$

30%測資滿足N , W_i , H_i <= 100

這是第1筆測資的示意圖：

這是第3筆測資的示意圖：

其中灰色框框代表已經開鎖的電腦。

Source:

JOI 2008/2009 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	5000ms	65536kb
0-2	5000ms	65536kb
0-3	5000ms	65536kb
1	5000ms	65536kb	10
2	5000ms	65536kb	10
3	5000ms	65536kb	10
4	5000ms	65536kb	10
5	5000ms	65536kb	10
6	5000ms	65536kb	10
7	5000ms	65536kb	10
8	5000ms	65536kb	10
9	5000ms	65536kb	10
10	5000ms	65536kb	10