Keinottelu kiinteistömarkkinoilla on stressaavaa työtä, jossa tulot ovat epävakaat. Auttaisiko asiaa, jos saisit vanhemmiltasi valtavan lainan ja pystyisit ennustamaan asuntojen hinnat tarkasti valittuina päivinä?

Aloitat ilman asuntoa, mutta pankkitilisi saldo on $10^{100}$. Koska sinulla ei ole kiinteistönvälittäjän lupaa, voit omistaa korkeintaan yhden asunnon kerrallaan. Olet jo katsellut tiettyä hyvällä paikalla sijaitsevaa asuntoa, ja juuri sen voit ostaa ja sitten myydä, mahdollisesti useita kertoja.

Alan portaali MyHouse on julkaissut ennustetut välit $[a_i, b_i]$ (missä $a_i < b_i$) asunnon hinnalle seuraavien $n$ päivän ajalle. Asunnon hinta $i$. päivänä on satunnainen reaaliluku $c_i$, joka valitaan tasajakautuneesti satunnaisesti väliltä $[a_i, b_i]$. Oletusarvoisesti saat tietää hinnan $c_i$ $i$. päivän alussa. Sinun on silloin päätettävä, teetkö kaupan. Jos omistat asunnon, voit myydä sen hintaan $c_i$, ja jos et omista sitä, voit ostaa sen hintaan $c_i$.

Vain tänään (ennen ensimmäistä päivää) MyHouse-portaali antaa uusien käyttäjien saada tietää tarkat hinnat $c_i$ valitulle $k$ päivän joukolle. Toisin sanoen valitset nyt $k$ päivän joukon ja saat tietää niiden hinnat, kun taas jokaisena jäljellä olevana $n - k$ päivänä saat tietää hinnan kyseisen päivän alussa.

$n$ päivän jälkeen sinun on päädyttävä tilanteeseen, jossa sinulla ei ole asuntoa; voittosi on pankkitilisi loppu- ja alkusaldon erotus. Määritä voiton suurin odotusarvo*, jos valitset $k$ päivän joukon optimaalisesti ja teet sen jälkeen kaupankäyntipäätökset optimaalisesti jokaisena $n$ päivänä.

*Odotusarvo on satunnaismuuttujan todennäköisyyksillä painotettu keskiarvo. Intuitiivisesti se on tulos, jonka odottaisit saavasi keskimäärin toistaessasi satunnaiskoetta monta kertaa.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), jotka kuvaavat päivien lukumäärää ja välittömästi tietoon saatavien hintojen lukumäärää.

Seuraavat $n$ riviä kuvaavat hintavälejä; $i$. rivi sisältää kaksi kokonaislukua $a_i$ ja $b_i$ ($1 \le a_i < b_i \le 10^6$).

Tuloste

Tulosta yksi reaaliluku – suurin mahdollinen voiton odotusarvo $n$ päivän jälkeen.

Sallittu suhteellinen tai absoluuttinen virhe on $10^{-6}$. Toisin sanoen, jos tulostat $x$ ja oikea tarkka tulos on $y$, on oltava $|x - y| \le 10^{-6} \cdot \max(1, y)$. Voit tulostaa enintään $20$ desimaalia pilkun jälkeen.

Esimerkit

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

Huomautus

Ensimmäisessä testissä $k = 0$, joten jokainen hinta saadaan tietää kyseisen päivän alussa. Optimaalinen strategia on ostaa asunto päivänä $1$ tai $2$ odotetulla kustannuksella $17.5$ ja myydä se sitten päivänä $3$ tai $4$ odotetulla tuotolla $46.25$. Odotettu voitto on $46.25 - 17.5 = 28.75$.

Toisessa testissä $k = 1$ ja meidän kannattaa optimaalisesti valita päivä $4$, jolloin saamme heti tietää reaaliluvun $c_4$ väliltä $[30, 60]$. Odotettu voitto on $31\frac{7}{18}$ optimaalisilla kaupankäyntipäätöksillä.

Kolmannessa testissä optimaalinen valinta $k$ päivän joukoksi on $\{2, 3, 6\}$. Saamme heti tietää hinnat $c_2$, $c_3$ ja $c_6$.