El Granjero Juan ha tenido problemas en hacer que sus plantas crezcan, y necesita su ayuda para irrigarlas adecuadamente. A usted se le proporciona las ubicaciones de ~N~ gotas de lluvia en el plano 2D, donde ~y~ representa la altura vertical de la gota, y ~x~ representa su ubicación sobre una recta numérica 1D:

Cada gota cae hacia abajo (hacia el eje x) con una velocidad de 1 unidad por segundo. A usted le gustaría colocar la maceta del Granjero Juan de ancho W en alguna parte del eje ~x~ de tal manera que la diferencia en tiempo entre que la primera gota toque la maceta y la última gota toque la maceta sea al menos una cantidad ~D~ (de tal manera que todas las flores en la maceta reciban bastante agua). Una gota de agua que caiga exactamente en el borde de la maceta cuenta como cayendo en la maceta.

Dado el valor de ~D~ y las ubicaciones de las ~N~ gotas, por favor calcule el mínimo valor posible de ~W~.

Entrada

• Línea 1: Dos enteros separados por espacio, ~N~ y ~D~.
• Líneas 2..1+N: La línea i+1 contiene las coordenadas ~(x,y)~ separadas por espacio de la gota ~i~, cada valor en el rango ~0...1,000,000~.

Salida

Un solo entero, dando el ancho mínimo posible de la maceta. Dé como salida ~-1~ si no es posible construir una maceta con el ancho suficiente para captura agua por al menos ~D~ unidades de tiempo.

Restricciones

• ~1 \leq N \leq 100,000~
• ~1 \leq D \leq 1,000,000~

Ejemplo de Entrada

4 5
6 3
2 4
4 10
12 15

Detalles de la Entrada: Hay 4 gotas, en las posiciones ~(6,3), (2,4), (4,10)~ y ~(12,15)~. La lluvia debe caer en la maceta por al menos 5 unidades de tiempo.

Ejemplo de Salida

2

Detalles de la Entrada: Una maceta de ancho 2 es necesaria y suficiente, desde que si la colocamos desde ~x=4..6~, entonces captura a las gotas #1 y #3, para una duración total de lluvia de ~10 -3 = 7~.

USACO 2012 March Contest, Silver Division Problem 2. Flowerpot.