시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB271887632.479%

문제

폭탄의 악마에게 x축 수직선 상에 있는 모든 폭탄을 터뜨리라 의뢰가 들어왔다. 현재 x축 수직선 상에는 총 $N$개의 폭탄이 있으며, 그중 $i$번째 폭탄의 폭발 비용은 $C_i$이다.

폭탄의 악마는 우선 원하는 만큼 폭탄을 선택할 수 있으며, 이때 총 폭발 비용은 선택한 폭탄의 폭발 비용의 합이다. 그 후, 힘을 $1$ 이상의 정수 $R$만큼 사용하여 선택한 모든 폭탄을 $R$만큼의 폭발 반경을 가지고 터뜨릴 수 있다. 이때, 폭탄이 터질 경우에 해당 폭탄의 반경 $R$ 내의 다른 모든 폭탄은 연쇄적으로 터지게 된다. 연쇄적으로 터진 폭탄도 마찬가지로 반경 $R$ 내의 다른 폭탄을 터뜨릴 수 있으며, 이는 반경 내에 더 이상 터질 폭탄이 없을 때까지 계속된다.

의뢰를 성공하려면 폭탄의 악마가 받은 의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 해야한다. 또한, 폭탄의 악마는 자신의 힘 $R$을 최소한으로 사용하고 싶어한다. 폭탄의 악마를 위해 의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 하는 폭탄의 악마의 힘 $R$의 최솟값을 구해주자.

입력

첫째 줄에 폭탄의 수 $N$이 주어진다. ($ 2 \le N \le 200\,000 $)

둘째 줄에 폭탄의 위치를 의미하는 정수 $X_1, X_2, \cdots , X_N$이 공백으로 구분되어 주어진다. $X_i$는 중복되어 주어지지 않는다. ($ -10^8 \le X_i \le 10^8 $)

셋째 줄에 비용을 의미하는 정수 $C_1, C_2, \cdots , C_N$이 공백으로 구분되어 주어진다. ($ 1 \le C_i \le 10\,000$)

넷째 줄에 폭탄의 악마가 받은 의뢰 비용을 의미하는 정수 $B$가 주어진다. ($ \min(C_i) \le B \le 10\,000\,000 $)

출력

의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 하는 폭탄의 악마의 힘 $R$의 최솟값을 출력한다.

예제 입력 1

5
1 3 6 10 13
5 2 3 4 1
7

예제 출력 1

3

예제 입력 2

7
4 11 0 2 7 15 20
2 8 3 6 5 1 4
10

예제 출력 2

4