Hay ~n~ segmentos (que no se intersectan) en el eje x. Se quiere mover los segmentos de tal forma que formen una zona continua, sin intersectarse (con la excepción de los extremos de los segmentos).

¿Cuál es la mínima suma de distancias que los segmentos se deben mover?

Entrada

La primera línea contiene el entero ~n \; (1 \leq n \leq 2000)~.

Cada una de las siguientes ~n~ líneas contienen los enteros ~a_i~ y ~b_i \; (0 \leq a_i \leq b_i \leq 10^9)~, estos son los extremos del ~i~-ésimo segmento.

Salida

En una única línea imprima la respuesta del problema.

Ejemplos

Entrada 1

3
1 3
6 9
15 16

Salida 1

9

Entrada 2

4
2 7
8 20
35 49
21 21

Salida 2

17

Explicación de los ejemplos

En el primer ejemplo se mueve el primer segmento ~3~ unidades hacia la derecha y el tercer segmento se mueve ~6~ unidades a la izquierda. Las coordenadas finales de los segmentos son:

• ~(4, 6)~
• ~(6, 9)~
• ~(9, 10)~

En el segundo ejemplo se mueve el primer segmento ~2~ unidades a la derecha, el segundo segmento ~1~ unidad a la derecha y el tercero ~14~ unidades a la izquierda. Las coordenadas finales de los segmentos son:

• ~(4, 9)~
• ~(9, 21)~
• ~(21, 35)~
• ~(21, 21)~