Spekulasjon i eiendomsmarkedet er stressende arbeid med ustabil inntekt. Ville det hjulpet hvis du fikk et enormt lån fra foreldrene dine og kunne forutsi leilighetsprisene nøyaktig på utvalgte dager?

Du starter uten leilighet, men bankinnskuddet ditt er $10^{100}$. Siden du mangler eiendomsmeglerbevilling, kan du eie høyst én leilighet om gangen. Du har allerede sett deg ut en bestemt leilighet med god beliggenhet, og det er denne du kan kjøpe og deretter selge, muligens flere ganger.

Bransjeportalen MyHouse har publisert forventede intervaller $[a_i, b_i]$ (med $a_i < b_i$) for leilighetens pris de neste $n$ dagene. Prisen på leiligheten den $i$-te dagen er et tilfeldig reelt tall $c_i$ valgt uniformt tilfeldig fra intervallet $[a_i, b_i]$. Som standard får du vite prisen $c_i$ på begynnelsen av den $i$-te dagen. Du må da bestemme om du vil gjennomføre en transaksjon. Hvis du eier leiligheten, kan du selge den for $c_i$, og hvis du ikke eier den, kan du kjøpe den for $c_i$.

Kun i dag (før den første dagen) lar MyHouse-portalen nye brukere få vite de nøyaktige prisene $c_i$ for en valgt mengde på $k$ dager. Det vil si at du nå velger en mengde på $k$ dager og får vite prisene deres, mens du for hver av de resterende $n - k$ dagene vil få vite prisen på begynnelsen av den dagen.

Etter $n$ dager må du ende opp uten leilighet; fortjenesten din er differansen mellom slutt- og startsaldoen din i banken. Bestem den maksimale forventningsverdien* for fortjenesten hvis du velger mengden på $k$ dager optimalt og deretter tar optimale transaksjonsbeslutninger på hver av de $n$ dagene.

*Forventningsverdien er gjennomsnittsverdien, vektet etter sannsynlighet, til en tilfeldig variabel. Intuitivt er det resultatet du i gjennomsnitt ville forvente når du gjentar et tilfeldig eksperiment mange ganger.

Inndata

Den første linjen inneholder to heltall $n$ og $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), som representerer henholdsvis antall dager og antall priser du kan få vite umiddelbart.

De neste $n$ linjene beskriver prisintervaller; den $i$-te linjen inneholder to heltall $a_i$ og $b_i$ ($1 \le a_i < b_i \le 10^6$).

Utdata

Skriv ut ett reelt tall – den maksimalt mulige forventningsverdien for fortjenesten etter $n$ dager.

Den akseptable relative eller absolutte feilen er $10^{-6}$. Det vil si at hvis du skriver ut $x$ og det korrekte eksakte resultatet er $y$, må det gjelde at $|x - y| \le 10^{-6} \cdot \max(1, y)$. Du kan skrive ut opptil $20$ sifre etter desimaltegnet.

Eksempler

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

Merk

I den første testen har vi $k = 0$, så hver pris blir kjent på begynnelsen av dagen. Det finnes en optimal strategi som går ut på å kjøpe leiligheten på dag $1$ eller $2$ til en forventet kostnad på $17.5$, og deretter selge den på dag $3$ eller $4$ med en forventet inntekt på $46.25$. Den forventede fortjenesten er $46.25 - 17.5 = 28.75$.

I den andre testen har vi $k = 1$ og vi bør optimalt velge dag $4$, slik at vi umiddelbart får vite et reelt tall $c_4$ fra intervallet $[30, 60]$. Den forventede fortjenesten er $31\frac{7}{18}$ ved optimale transaksjonsbeslutninger.

I den tredje testen er det optimale valget av mengden på $k$ dager $\{2, 3, 6\}$. Vi får umiddelbart vite prisene $c_2$, $c_3$ og $c_6$.