Spekulation på fastighetsmarknaden är ett stressigt arbete med ostadiga inkomster. Skulle det hjälpa om du fick ett enormt lån från dina föräldrar och exakt kunde förutsäga lägenhetspriser på utvalda dagar?

Du börjar utan lägenhet, men ditt banksaldo är $10^{100}$. Eftersom du saknar mäklarlicens får du äga högst en lägenhet åt gången. Du har redan spanat in en specifik lägenhet med bra läge, och det är den du kan köpa och sedan sälja, eventuellt flera gånger.

Branschportalen MyHouse har publicerat förväntade intervall $[a_i, b_i]$ (med $a_i < b_i$) för lägenhetens pris under de kommande $n$ dagarna. Priset på lägenheten den $i$-te dagen är ett slumpmässigt reellt tal $c_i$ som väljs likformigt slumpmässigt från intervallet $[a_i, b_i]$. Som standard får du reda på priset $c_i$ i början av den $i$-te dagen. Du måste då bestämma om du ska genomföra en transaktion. Om du äger lägenheten får du sälja den för $c_i$, och om du inte äger den får du köpa den för $c_i$.

Endast idag (före den första dagen) låter portalen MyHouse nya användare få reda på de exakta priserna $c_i$ för en vald mängd av $k$ dagar. Det vill säga, du väljer nu en mängd av $k$ dagar och får veta deras priser, medan du för var och en av de återstående $n - k$ dagarna får veta priset i början av den dagen.

Efter $n$ dagar måste du sluta utan lägenhet; din vinst är skillnaden mellan ditt slutliga och ditt ursprungliga banksaldo. Bestäm det maximala väntevärdet* för vinsten om du optimalt väljer mängden av $k$ dagar och sedan optimalt fattar transaktionsbeslut under var och en av de $n$ dagarna.

*Väntevärdet är medelvärdet, viktat med sannolikhet, för en slumpvariabel. Intuitivt är det resultatet du i genomsnitt skulle förvänta dig om du upprepade ett slumpmässigt experiment många gånger.

Indata

Den första raden innehåller två heltal $n$ och $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), som representerar antalet dagar respektive antalet priser du får veta omedelbart.

De följande $n$ raderna beskriver prisintervall; den $i$-te raden innehåller två heltal $a_i$ och $b_i$ ($1 \le a_i < b_i \le 10^6$).

Utdata

Skriv ut ett reellt tal – det maximalt möjliga väntevärdet för vinsten efter $n$ dagar.

Det acceptabla relativa eller absoluta felet är $10^{-6}$. Det vill säga, om du skriver ut $x$ och det korrekta exakta resultatet är $y$, måste det gälla att $|x - y| \le 10^{-6} \cdot \max(1, y)$. Du kan skriva ut upp till $20$ siffror efter decimaltecknet.

Exempel

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

Anmärkning

I det första testet har vi $k = 0$, så varje pris blir känt i början av respektive dag. Det finns en optimal strategi att köpa lägenheten dag $1$ eller $2$ till en förväntad kostnad av $17.5$, och sedan sälja den dag $3$ eller $4$ med en förväntad inkomst på $46.25$. Den förväntade vinsten är $46.25 - 17.5 = 28.75$.

I det andra testet har vi $k = 1$ och vi bör optimalt välja dag $4$, så att vi omedelbart får veta ett reellt tal $c_4$ från intervallet $[30, 60]$. Den förväntade vinsten är $31\frac{7}{18}$ vid optimala transaktionsbeslut.

I det tredje testet är det optimala valet av mängden av $k$ dagar $\{2, 3, 6\}$. Vi får omedelbart veta priserna $c_2$, $c_3$ och $c_6$.