Spekulationen auf dem Immobilienmarkt sind eine stressige Arbeit mit unsicheren Einnahmen. Würde es helfen, wenn du einen riesigen Kredit von deinen Eltern bekämst und die Wohnungspreise an ausgewählten Tagen präzise vorhersagen könntest?

Du beginnst ohne Wohnung, aber dein Kontostand beträgt $10^{100}$. Da dir eine Immobilienmaklerlizenz fehlt, darfst du zu jedem Zeitpunkt höchstens eine Wohnung besitzen. Du hast bereits eine bestimmte Wohnung in guter Lage ins Auge gefasst, und genau diese kannst du kaufen und dann wieder verkaufen – möglicherweise auch mehrmals.

Das Branchenportal MyHouse hat prognostizierte Intervalle $[a_i, b_i]$ (mit $a_i < b_i$) für den Preis der Wohnung in den nächsten $n$ Tagen veröffentlicht. Der Preis der Wohnung am $i$-ten Tag ist eine zufällige reelle Zahl $c_i$, die gleichverteilt zufällig aus dem Intervall $[a_i, b_i]$ gewählt wird. Standardmäßig erfährst du den Preis $c_i$ zu Beginn des $i$-ten Tages. Du musst dann entscheiden, ob du eine Transaktion tätigst. Wenn du die Wohnung besitzt, kannst du sie für $c_i$ verkaufen, und wenn du sie nicht besitzt, kannst du sie für $c_i$ kaufen.

Nur heute (vor dem ersten Tag) erlaubt das Portal MyHouse neuen Nutzern, die genauen Preise $c_i$ für eine ausgewählte Menge von $k$ Tagen zu erfahren. Das heißt, du wählst jetzt eine Menge von $k$ Tagen aus und erfährst deren Preise, während du für jeden der verbleibenden $n - k$ Tage den Preis erst zu Beginn des jeweiligen Tages erfährst.

Nach $n$ Tagen musst du ohne Wohnung enden; dein Gewinn ist die Differenz zwischen deinem endgültigen und deinem anfänglichen Kontostand. Bestimme den maximalen Erwartungswert* des Gewinns, wenn du die Menge von $k$ Tagen optimal wählst und dann an jedem der $n$ Tage optimale Transaktionsentscheidungen triffst.

*Der Erwartungswert ist der mit der Wahrscheinlichkeit gewichtete Durchschnittswert einer Zufallsvariablen. Anschaulich ist es das Ergebnis, das man im Durchschnitt erwarten würde, wenn man ein Zufallsexperiment sehr oft wiederholt.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), die die Anzahl der Tage bzw. die Anzahl der Preise darstellen, die du sofort erfahren darfst.

Die nächsten $n$ Zeilen beschreiben die Preisintervalle; die $i$-te Zeile enthält zwei ganze Zahlen $a_i$ und $b_i$ ($1 \le a_i < b_i \le 10^6$).

Ausgabe

Gib eine reelle Zahl aus – den maximal möglichen Erwartungswert des Gewinns nach $n$ Tagen.

Der akzeptable relative oder absolute Fehler beträgt $10^{-6}$. Das heißt, wenn du $x$ ausgibst und das korrekte exakte Ergebnis $y$ ist, muss $|x - y| \le 10^{-6} \cdot \max(1, y)$ gelten. Du darfst bis zu $20$ Nachkommastellen ausgeben.

Beispiele

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

Hinweis

Im ersten Test gilt $k = 0$, sodass jeder Preis zu Beginn seines Tages erfahren wird. Es gibt eine optimale Strategie, die Wohnung an Tag $1$ oder $2$ zu erwarteten Kosten von $17.5$ zu kaufen und sie dann an Tag $3$ oder $4$ mit einem erwarteten Erlös von $46.25$ zu verkaufen. Der erwartete Gewinn beträgt $46.25 - 17.5 = 28.75$.

Im zweiten Test gilt $k = 1$ und wir sollten optimalerweise Tag $4$ wählen, sodass wir sofort eine reelle Zahl $c_4$ aus dem Intervall $[30, 60]$ erfahren. Der erwartete Gewinn beträgt bei optimalen Transaktionsentscheidungen $31\frac{7}{18}$.

Im dritten Test ist die optimale Wahl der Menge von $k$ Tagen $\{2, 3, 6\}$. Wir erfahren sofort die Preise $c_2$, $c_3$ und $c_6$.