Spekulacja na rynku nieruchomości to stresująca praca o niestabilnych zarobkach. Czy pomogłoby, gdybyś dostał ogromną pożyczkę od rodziców i mógł dokładnie przewidzieć ceny mieszkań w wybrane dni?

Zaczynasz bez mieszkania, ale stan twojego konta bankowego wynosi $10^{100}$. Ponieważ nie masz licencji pośrednika w obrocie nieruchomościami, możesz posiadać co najwyżej jedno mieszkanie naraz. Wypatrzyłeś już konkretne mieszkanie w dobrej lokalizacji i to właśnie je możesz kupować, a następnie sprzedawać, być może wielokrotnie.

Portal branżowy MyHouse opublikował przewidywane przedziały $[a_i, b_i]$ (gdzie $a_i < b_i$) ceny tego mieszkania na kolejne $n$ dni. Cena mieszkania $i$-tego dnia jest losową liczbą rzeczywistą $c_i$ wybraną jednostajnie losowo z przedziału $[a_i, b_i]$. Domyślnie poznajesz cenę $c_i$ na początku $i$-tego dnia. Musisz wtedy zdecydować, czy dokonujesz transakcji. Jeśli posiadasz mieszkanie, możesz je sprzedać za $c_i$, a jeśli go nie posiadasz, możesz je kupić za $c_i$.

Tylko dzisiaj (przed pierwszym dniem) portal MyHouse pozwala nowym użytkownikom poznać dokładne ceny $c_i$ dla wybranego zbioru $k$ dni. To znaczy, teraz wybierasz zbiór $k$ dni i poznajesz ich ceny, natomiast dla każdego z pozostałych $n - k$ dni poznasz cenę na początku danego dnia.

Po $n$ dniach musisz zakończyć bez mieszkania; twój zysk to różnica między końcowym a początkowym stanem konta bankowego. Wyznacz maksymalną wartość oczekiwaną* zysku, jeśli optymalnie wybierzesz zbiór $k$ dni, a następnie będziesz optymalnie podejmować decyzje transakcyjne w każdym z $n$ dni.

*Wartość oczekiwana to średnia wartość zmiennej losowej ważona prawdopodobieństwem. Intuicyjnie jest to wynik, którego średnio należałoby się spodziewać przy wielokrotnym powtarzaniu eksperymentu losowego.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), oznaczające odpowiednio liczbę dni oraz liczbę cen, które możesz poznać natychmiast.

Kolejne $n$ wierszy opisuje przedziały cenowe; $i$-ty wiersz zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i < b_i \le 10^6$).

Wyjście

Wypisz jedną liczbę rzeczywistą – maksymalną możliwą wartość oczekiwaną zysku po $n$ dniach.

Dopuszczalny błąd względny lub bezwzględny wynosi $10^{-6}$. Oznacza to, że jeśli wypiszesz $x$, a poprawny dokładny wynik to $y$, musi zachodzić $|x - y| \le 10^{-6} \cdot \max(1, y)$. Możesz wypisać do $20$ cyfr po kropce dziesiętnej.

Przykłady

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

Uwaga

W pierwszym teście mamy $k = 0$, więc każdą cenę poznajemy na początku danego dnia. Istnieje optymalna strategia polegająca na kupnie mieszkania dnia $1$ lub $2$ przy oczekiwanym koszcie $17.5$, a następnie sprzedaży go dnia $3$ lub $4$ przy oczekiwanym przychodzie $46.25$. Oczekiwany zysk wynosi $46.25 - 17.5 = 28.75$.

W drugim teście mamy $k = 1$ i optymalnie powinniśmy wybrać dzień $4$, dzięki czemu natychmiast poznajemy liczbę rzeczywistą $c_4$ z przedziału $[30, 60]$. Oczekiwany zysk wynosi $31\frac{7}{18}$ przy optymalnych decyzjach transakcyjnych.

W trzecim teście optymalnym wyborem zbioru $k$ dni jest $\{2, 3, 6\}$. Natychmiast poznajemy ceny $c_2$, $c_3$ oraz $c_6$.