ICPC Camp

John은 올해 북미 ICPC 합숙 훈련 캠프를 이끄는 총책임자이다. 캠프는 여러 날 동안 진행된다. 매일 고전 문제 하나와 창의 문제 하나, 두 문제를 소개하는 강의가 열린다. 각 문제는 캠프 전체에서 한 번만 소개할 수 있다. 모든 문제에는 정수 난이도가 매겨져 있다.

John은 매일의 강의가 너무 부담스럽지 않아야 한다고 생각한다. 따라서 하루에 소개하는 두 문제의 난이도 합은 정해진 값을 넘지 않아야 한다. 또한 같은 날 두 문제의 난이도는 대략 비슷해야 한다. 어느 날에 소개하는 두 문제의 난이도 차의 절댓값을 d라 하자. 모든 d 중 최댓값을 D라 할 때, D는 가능한 한 작아야 한다.

John이 문제를 잘 고르고 잘 배치했을 때, n일 동안의 ICPC 합숙 훈련 캠프에서 그가 달성할 수 있는 가장 작은 D는 얼마인가?

첫째 줄에 공백으로 구분된 네 정수 n, p, q (1 ≤ n, p, q ≤ 2 · 105, n ≤ min(p, q))와 s (0 ≤ s ≤ 109)가 주어진다. n은 캠프의 일수, p는 고전 문제의 수, q는 창의 문제의 수, s는 하루에 소개하는 두 문제 난이도 합의 최댓값이다.

다음 p개 줄에 각각 정수 x (0 ≤ x ≤ 109)가 주어진다. 이는 p개 고전 문제의 난이도이다.

그다음 q개 줄에 각각 정수 y (0 ≤ y ≤ 109)가 주어진다. 이는 q개 창의 문제의 난이도이다.

John이 n일의 훈련 동안 문제를 선택해 달성할 수 있는 가장 작은 D를 정수 하나로 출력한다. n일 동안 문제를 선택할 방법이 없으면 −1을 출력한다.