La speculazione nel mercato immobiliare è un lavoro stressante con guadagni instabili. Sarebbe d'aiuto ricevere un enorme prestito dai tuoi genitori e poter prevedere con precisione i prezzi degli appartamenti in giorni selezionati?

Inizi senza un appartamento, ma il tuo saldo bancario è $10^{100}$. Poiché non hai la licenza di agente immobiliare, puoi possedere al massimo un appartamento alla volta. Hai già adocchiato uno specifico appartamento in una buona posizione, ed è quello che puoi comprare e poi vendere, eventualmente più volte.

Il portale di settore MyHouse ha pubblicato gli intervalli previsti $[a_i, b_i]$ (con $a_i < b_i$) del prezzo dell'appartamento per i prossimi $n$ giorni. Il prezzo dell'appartamento nell'$i$-esimo giorno è un numero reale casuale $c_i$ scelto uniformemente a caso dall'intervallo $[a_i, b_i]$. Di norma, scopri il prezzo $c_i$ all'inizio dell'$i$-esimo giorno. Devi quindi decidere se effettuare una transazione. Se possiedi l'appartamento, puoi venderlo per $c_i$, mentre se non lo possiedi, puoi comprarlo per $c_i$.

Solo oggi (prima del primo giorno) il portale MyHouse consente ai nuovi utenti di conoscere i prezzi esatti $c_i$ per un insieme scelto di $k$ giorni. Cioè, ora scegli un insieme di $k$ giorni e ne scopri i prezzi, mentre per ciascuno dei restanti $n - k$ giorni scoprirai il prezzo all'inizio di quel giorno.

Dopo $n$ giorni devi terminare senza un appartamento; il tuo profitto è la differenza tra il tuo saldo bancario finale e quello iniziale. Determina il massimo valore atteso* del profitto, se scegli in modo ottimale l'insieme di $k$ giorni e poi prendi in modo ottimale le decisioni di transazione in ciascuno degli $n$ giorni.

*Il valore atteso è il valore medio, ponderato per la probabilità, di una variabile casuale. Intuitivamente, è il risultato che ti aspetteresti in media ripetendo molte volte un esperimento casuale.

Input

La prima riga contiene due interi $n$ e $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), che rappresentano rispettivamente il numero di giorni e il numero di prezzi che puoi conoscere immediatamente.

Le successive $n$ righe descrivono gli intervalli di prezzo; l'$i$-esima riga contiene due interi $a_i$ e $b_i$ ($1 \le a_i < b_i \le 10^6$).

Output

Stampa un numero reale – il massimo valore atteso possibile del profitto dopo $n$ giorni.

L'errore relativo o assoluto accettabile è $10^{-6}$. Cioè, se stampi $x$ e il risultato esatto corretto è $y$, allora deve valere $|x - y| \le 10^{-6} \cdot \max(1, y)$. Puoi stampare fino a $20$ cifre dopo il punto decimale.

Esempi

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

Note

Nel primo test abbiamo $k = 0$, quindi ogni prezzo viene scoperto all'inizio del relativo giorno. Esiste una strategia ottimale che consiste nel comprare l'appartamento il giorno $1$ o $2$ a un costo atteso di $17.5$, per poi venderlo il giorno $3$ o $4$ con un ricavo atteso di $46.25$. Il profitto atteso è $46.25 - 17.5 = 28.75$.

Nel secondo test abbiamo $k = 1$ e la scelta ottimale è il giorno $4$, cosicché scopriamo immediatamente un numero reale $c_4$ dall'intervallo $[30, 60]$. Il profitto atteso è $31\frac{7}{18}$ per decisioni di transazione ottimali.

Nel terzo test la scelta ottimale dell'insieme di $k$ giorni è $\{2, 3, 6\}$. Scopriamo immediatamente i prezzi $c_2$, $c_3$ e $c_6$.