题目描述

约翰是今年北美 ICPC 训练营的主要组织者。训练营持续数天。每天会有一场讲座，介绍两道题：一道经典题和一道创意题。每道题在整个训练营期间只会被介绍一次。每道题都有一个整数难度值。

约翰知道，每天的讲座不应过于繁重。因此，同一天两道题的难度之和不得超过某个固定值。此外，每天的两道题难度应大致相当。设 $d$ 为某天介绍的两道题难度之差的绝对值，定义 $D$ 为所有 $d$ 中的最大值。约翰希望 $D$ 尽可能小。

如果约翰精心挑选题目并合理安排，对于 $n$ 天的 ICPC 训练营，他能达到的最小 $D$ 是多少？

输入格式

输入的第一行包含四个空格分隔的整数 $n$、$p$、$q$（$1 \le n, p, q \le 2 \cdot 10^5$，$n \le \min(p, q)$）和 $s$（$0 \le s \le 10^9$），其中 $n$ 是训练营的天数，$p$ 是经典题的数量，$q$ 是创意题的数量，$s$ 是任意一天中两道题难度之和的最大允许值。

接下来的 $p$ 行，每行包含一个整数 $x$（$0 \le x \le 10^9$），表示 $p$ 道经典题的难度。

接下来的 $q$ 行，每行包含一个整数 $y$（$0 \le y \le 10^9$），表示 $q$ 道创意题的难度。

输出格式

输出一个整数，表示约翰能达到的最小 $D$；如果无法为 $n$ 个训练日选出题目，则输出 $-1$。

4 5 5 10
1
3
3
4
9
0
2
5
7
8

4

4 4 4 15
1
5
10
12
1
3
10
14

13

4 4 4 10
1
12
5
10
1
10
3
14

-1

提示

翻译由 DeepSeek V3.2 完成