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 |