2020 ICPC North America Championship — Open Division

Start

2020-02-22 06:15 AKST

2020 ICPC North America Championship — Open Division

End

2020-02-22 11:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -240 days 20:28:27

Time elapsed

4:45:00

Time remaining

0:00:00

Problem G
ICPC Camp

John is a leading organizer of this year’s North America ICPC training camp. The camp lasts several days. On each day, there will be a lecture introducing two problems: one classical problem and one creative problem. Each problem can only be introduced once during the entire camp. Every problem has an integer difficulty level.

John knows that the lecture on each day should not be too overwhelming. Therefore, the sum of the difficulties of the two problems in a single day shall not exceed some fixed value. Also, the two problems on each day should be roughly on the same level. Let $d$’s be the absolute difference between the difficulties of the two problems introduced on any given day. The maximum of all of the $d$s, defined as $D$, should be as small as possible.

If John chooses problems well and arranges them wisely, what is the smallest $D$ he can achieve for the $n$ days of the ICPC training camp?

Input

The first line of input contains four space-separated integers $n$, $p$, $q$ ($1 \leq n, p, q \leq 2 \cdot 10^5$,
$n \leq \min (p, q)$) and $s$ ($0 \leq s \leq 10^9$), where $n$ is the number of days of the camp, $p$ is the number of classical problems, $q$ is the number of creative problems, and $s$ is the maximum sum of difficulties on any given day.

Each of the next $p$ lines contains an integer $x$ ($0 \le x \le 10^9$). These are difficulties of the $p$ classical problems.

Each of the next $q$ lines contains an integer $y$ ($0 \le y \le 10^9$). These are difficulties of the $q$ creative problems.

Output

Output a single integer, which is the smallest $D$ John can achieve, or $-1$ if there is no way John can select problems for the $n$ training days.

Sample Input 1 Sample Output 1
3 4 5 10
3
4
4
9
0
1
5
6
6
2
Sample Input 2 Sample Output 2
4 4 4 15
1
5
10
12
1
3
10
14
13
Sample Input 3 Sample Output 3
4 4 4 10
1
12
5
10
1
10
3
14
-1