Spekulasi di pasar real estat adalah pekerjaan penuh tekanan dengan penghasilan yang tidak stabil. Apakah akan membantu jika Anda mendapatkan pinjaman besar dari orang tua Anda dan dapat memprediksi harga apartemen secara tepat pada hari-hari tertentu?

Anda mulai tanpa apartemen, tetapi saldo bank Anda adalah $10^{100}$. Karena Anda tidak memiliki lisensi agen real estat, Anda hanya boleh memiliki paling banyak satu apartemen pada satu waktu. Anda sudah mengincar sebuah apartemen tertentu di lokasi yang bagus, dan itulah apartemen yang dapat Anda beli lalu jual, mungkin berkali-kali.

Portal industri MyHouse telah menerbitkan interval prediksi $[a_i, b_i]$ (dengan $a_i < b_i$) dari harga apartemen untuk $n$ hari ke depan. Harga apartemen pada hari ke-$i$ adalah bilangan real acak $c_i$ yang dipilih secara acak seragam dari interval $[a_i, b_i]$. Secara bawaan, Anda mengetahui harga $c_i$ pada awal hari ke-$i$. Anda kemudian harus memutuskan apakah akan melakukan transaksi. Jika Anda memiliki apartemen tersebut, Anda dapat menjualnya seharga $c_i$, dan jika Anda tidak memilikinya, Anda dapat membelinya seharga $c_i$.

Hanya hari ini (sebelum hari pertama) portal MyHouse mengizinkan pengguna baru untuk mengetahui harga pasti $c_i$ untuk suatu himpunan $k$ hari yang dipilih. Artinya, Anda sekarang memilih himpunan $k$ hari dan mengetahui harganya, sedangkan untuk masing-masing dari $n - k$ hari sisanya Anda akan mengetahui harganya pada awal hari tersebut.

Setelah $n$ hari Anda harus berakhir tanpa apartemen; keuntungan Anda adalah selisih antara saldo bank akhir dan awal Anda. Tentukan nilai ekspektasi* maksimum dari keuntungan tersebut, jika Anda memilih himpunan $k$ hari secara optimal dan kemudian membuat keputusan transaksi secara optimal pada masing-masing dari $n$ hari.

*Nilai ekspektasi adalah nilai rata-rata, dibobot dengan probabilitas, dari suatu variabel acak. Secara intuitif, ini adalah hasil yang Anda harapkan secara rata-rata ketika mengulangi percobaan acak berkali-kali.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), yang masing-masing menyatakan jumlah hari dan jumlah harga yang dapat Anda ketahui secara langsung.

$n$ baris berikutnya mendeskripsikan interval harga; baris ke-$i$ berisi dua bilangan bulat $a_i$ dan $b_i$ ($1 \le a_i < b_i \le 10^6$).

Keluaran

Cetak satu bilangan real – nilai ekspektasi maksimum yang mungkin dari keuntungan setelah $n$ hari.

Galat relatif atau absolut yang dapat diterima adalah $10^{-6}$. Artinya, jika Anda mencetak $x$ dan hasil eksak yang benar adalah $y$, maka harus berlaku $|x - y| \le 10^{-6} \cdot \max(1, y)$. Anda dapat mencetak hingga $20$ digit di belakang koma.

Contoh

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

Catatan

Pada uji pertama kita memiliki $k = 0$, sehingga setiap harga diketahui pada awal harinya. Terdapat strategi optimal yaitu membeli apartemen pada hari ke-$1$ atau ke-$2$ dengan ekspektasi biaya $17.5$, lalu menjualnya pada hari ke-$3$ atau ke-$4$ dengan ekspektasi pendapatan $46.25$. Ekspektasi keuntungannya adalah $46.25 - 17.5 = 28.75$.

Pada uji kedua kita memiliki $k = 1$ dan kita sebaiknya secara optimal memilih hari ke-$4$, sehingga kita langsung mengetahui sebuah bilangan real $c_4$ dari interval $[30, 60]$. Ekspektasi keuntungannya adalah $31\frac{7}{18}$ untuk keputusan transaksi yang optimal.

Pada uji ketiga pilihan optimal untuk himpunan $k$ hari adalah $\{2, 3, 6\}$. Kita langsung mengetahui harga $c_2$, $c_3$, dan $c_6$.