Segmentos sin Intersección


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Python 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

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)

Comments

There are no comments at the moment.