La especulación en el mercado inmobiliario es un trabajo estresante con ingresos inestables. ¿Ayudaría si consiguieras un préstamo enorme de tus padres y pudieras predecir con precisión los precios de los apartamentos en días seleccionados?
Empiezas sin apartamento, pero tu saldo bancario es de $10^{100}$. Como careces de licencia de agente inmobiliario, puedes poseer como máximo un apartamento a la vez. Ya has fichado un apartamento específico en una buena ubicación, y ese es el que puedes comprar y luego vender, posiblemente varias veces.
El portal del sector MyHouse ha publicado intervalos predichos $[a_i, b_i]$ (con $a_i < b_i$) del precio del apartamento para los próximos $n$ días. El precio del apartamento en el $i$-ésimo día es un número real aleatorio $c_i$ elegido uniformemente al azar del intervalo $[a_i, b_i]$. Por defecto, conoces el precio $c_i$ al principio del $i$-ésimo día. Entonces debes decidir si realizas una transacción. Si posees el apartamento, puedes venderlo por $c_i$, y si no lo posees, puedes comprarlo por $c_i$.
Solo hoy (antes del primer día), el portal MyHouse permite a los nuevos usuarios conocer los precios exactos $c_i$ para un conjunto elegido de $k$ días. Es decir, ahora eliges un conjunto de $k$ días y conoces sus precios, mientras que para cada uno de los $n - k$ días restantes conocerás el precio al principio de ese día.
Después de $n$ días debes terminar sin apartamento; tu beneficio es la diferencia entre tu saldo bancario final e inicial. Determina el máximo valor esperado* del beneficio, si eliges de forma óptima el conjunto de $k$ días y luego tomas de forma óptima las decisiones de transacción en cada uno de los $n$ días.
*El valor esperado es el valor promedio, ponderado por probabilidad, de una variable aleatoria. Intuitivamente, es el resultado que esperarías obtener de media al repetir un experimento aleatorio muchas veces.
Entrada
La primera línea contiene dos enteros $n$ y $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), que representan respectivamente el número de días y el número de precios que puedes conocer de inmediato.
Las siguientes $n$ líneas describen los intervalos de precios; la $i$-ésima línea contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i < b_i \le 10^6$).
Salida
Imprime un número real – el máximo valor esperado posible del beneficio después de $n$ días.
El error relativo o absoluto aceptable es $10^{-6}$. Es decir, si imprimes $x$ y el resultado exacto correcto es $y$, entonces debe cumplirse que $|x - y| \le 10^{-6} \cdot \max(1, y)$. Puedes imprimir hasta $20$ dígitos después del punto decimal.
Ejemplos
input
4 0 10 30 10 30 40 50 30 60
output
28.75
input
4 1 10 30 10 30 40 50 30 60
output
31.3888888889
input
6 3 10 50 30 70 50 70 30 50 30 40 10 40
output
33.6805555556
Nota
En la primera prueba tenemos $k = 0$, por lo que cada precio se conoce al principio de su día. Existe una estrategia óptima que consiste en comprar el apartamento el día $1$ o $2$ a un coste esperado de $17.5$, y luego venderlo el día $3$ o $4$ con un ingreso esperado de $46.25$. El beneficio esperado es $46.25 - 17.5 = 28.75$.
En la segunda prueba tenemos $k = 1$ y deberíamos elegir de forma óptima el día $4$, de modo que conocemos inmediatamente un número real $c_4$ del intervalo $[30, 60]$. El beneficio esperado es $31\frac{7}{18}$ para decisiones de transacción óptimas.
En la tercera prueba, la elección óptima del conjunto de $k$ días es $\{2, 3, 6\}$. Conocemos inmediatamente los precios $c_2$, $c_3$ y $c_6$.