Descripción

¡Te han contratado para construir un sistema de ascensores para un hotel!

El hotel tiene ~k~ ascensores, e inicialmente puedes elegir en qué pisos están. Durante el día hay ~n~ solicitudes, cada una caracterizada por un par ~(l, ?)~. Esto significa que alguien está en el l-ésimo piso y quiere ir al r-ésimo piso.

A la gente no le gusta esperar, por lo que tenemos el requisito de completar las solicitudes de forma secuencial. Más formalmente, la solicitud de número ~i~ debe completarse antes que la solicitud de número ~i + 1~.

Los ascensores son pequeños y deben estar vacíos o transportar exactamente a un pasajero en un momento dado.

Además, cada petición puede ser completada por cualquiera de los ascensores.

Queremos construir un sistema inteligente, por lo que queremos minimizar el número total de pisos cuando los ascensores viajan vacíos. Más precisamente, si un ascensor viaja desde el piso ~p~ al piso ~q~ sin pasajero, entonces consideramos que ha viajado |~p - ?~| pisos vacios.

Desafortunadamente, el hotel es viejo y las máquinas solo tienen 64 MB de memoria. Sin embargo, sabemos que eres un gran programador, así que esto no debería ser un problema para ti.

Tarea

Escribe un programa que calcule la forma óptima que minimice el número total de pisos en los que los ascensores viajan vacíos.

Entrada

La primera línea de la entrada contiene los números ~n~ y ~k~.

Las siguientes ~n~ líneas contienen ~2~ números cada una - ~(l, r)~ por solicitud.

Salida

En la línea única de la salida, imprima la suma mínima de pisos donde los ascensores viajan vacíos.

Restricciones

~1 \le n \le 10 000~

~1 \le k \le?in (30, n)~

~1 \le l, r \le 10^9~

Subtareas

1 para ~n \le 22~ | puntos 5

2 para ~n \le 250~ | puntos 20

3 para ~n \le 600~ | puntos 10

4 para ~n \le 1250~ | puntos 15

5 para ~n \le 2500~ | puntos 20

6 para - | puntos 30

Ejemplo de Entrada

3 2
5 20
8 100
2 80

Ejemplo de Salida

12

Explicación del ejemplo

El ascensor ~1~ está inicialmente en el piso ~5~ y el ascensor ~2~ está en el piso ~8~.

El ascensor ~1~ viaja ~0~ pisos vacío y transporta al pasajero al piso ~20~.

El ascensor ~1~ viaja ~12~ pisos vacíos y transporta al pasajero al piso ~100~.

El ascensor ~2~ viaja ~0~ pisos vacíos y transporta al pasajero al piso ~80~.

El número total de pisos donde los ascensores viajan vacíos es ~0 + 12 + 0 = 12~.