화분

농부 존은 식물을 잘 기르지 못해 어려움을 겪고 있으며, 물을 제대로 주기 위해 당신의 도움이 필요하다. 2차원 평면 위에 있는 $N$개 빗방울($1 \le N \le 100{,}000$)의 위치가 주어진다. 여기서 $y$는 빗방울의 수직 높이를, $x$는 1차원 수직선 위에서의 위치를 나타낸다.

각 빗방울은 매초 $1$단위의 속도로 아래(x축 방향)로 떨어진다. 농부 존의 폭 $W$짜리 화분을 x축 위 어딘가에 놓아, 화분에 처음으로 떨어지는 빗방울과 마지막으로 떨어지는 빗방울 사이의 시간 차이가 적어도 $D$ 이상이 되도록 하고 싶다(그래야 화분 속 꽃이 충분한 물을 받는다). 화분의 가장자리에 정확히 떨어지는 빗방울도 화분에 떨어진 것으로 센다.

$D$ 값과 $N$개 빗방울의 위치가 주어졌을 때, 가능한 화분 폭 $W$의 최솟값을 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $D$가 주어진다 ($1 \le D \le 1{,}000{,}000$).
• 둘째 줄부터 $N$개의 줄: $i+1$번째 줄에는 빗방울 $i$의 좌표 $x$와 $y$가 공백으로 구분되어 주어진다. 각 값은 $0$ 이상 $1{,}000{,}000$ 이하이다.

• 화분 폭의 최솟값을 정수 하나로 출력한다. 적어도 $D$ 시간 동안 비를 받을 만큼 넓은 화분을 만들 수 없다면 $-1$을 출력한다.

빗방울이 x축에 닿기까지 걸리는 시간은 그 높이 $y$와 같다. 따라서 화분이 잡는 빗방울들 중 가장 큰 $y$와 가장 작은 $y$의 차이가 $D$ 이상이 되어야 한다. 예를 들어 빗방울이 $(6,3)$, $(2,4)$, $(4,10)$, $(12,15)$에 있고 비가 적어도 $5$ 시간 동안 화분에 떨어져야 한다면, 폭 $2$의 화분이면 충분하다. 화분을 $x=4$부터 $x=6$까지 놓으면 빗방울 1번과 3번을 잡아 총 $10-3=7$ 시간 동안 비를 받기 때문이다.