Đầu cơ trên thị trường bất động sản là một công việc căng thẳng với thu nhập bấp bênh. Liệu mọi chuyện có dễ dàng hơn nếu bạn nhận được một khoản vay khổng lồ từ bố mẹ và có thể dự đoán chính xác giá căn hộ vào những ngày được chọn?

Bạn bắt đầu mà không có căn hộ nào, nhưng số dư ngân hàng của bạn là $10^{100}$. Vì không có chứng chỉ môi giới bất động sản, bạn chỉ được sở hữu tối đa một căn hộ tại một thời điểm. Bạn đã nhắm được một căn hộ cụ thể ở vị trí đẹp, và đó là căn hộ mà bạn có thể mua rồi bán, có thể nhiều lần.

Cổng thông tin bất động sản MyHouse đã công bố các khoảng dự đoán $[a_i, b_i]$ (với $a_i < b_i$) cho giá của căn hộ trong $n$ ngày tới. Giá của căn hộ vào ngày thứ $i$ là một số thực ngẫu nhiên $c_i$ được chọn ngẫu nhiên phân bố đều từ đoạn $[a_i, b_i]$. Mặc định, bạn biết được giá $c_i$ vào đầu ngày thứ $i$. Sau đó bạn phải quyết định có thực hiện giao dịch hay không. Nếu đang sở hữu căn hộ, bạn có thể bán nó với giá $c_i$, và nếu chưa sở hữu nó, bạn có thể mua nó với giá $c_i$.

Chỉ riêng hôm nay (trước ngày đầu tiên), cổng thông tin MyHouse cho phép người dùng mới biết trước giá chính xác $c_i$ của một tập hợp gồm $k$ ngày tự chọn. Nghĩa là bây giờ bạn chọn một tập hợp gồm $k$ ngày và biết giá của chúng, trong khi với mỗi ngày trong $n - k$ ngày còn lại, bạn sẽ biết giá vào đầu ngày hôm đó.

Sau $n$ ngày, bạn phải kết thúc ở trạng thái không sở hữu căn hộ nào; lợi nhuận của bạn là hiệu số giữa số dư ngân hàng cuối cùng và số dư ban đầu. Hãy xác định giá trị kỳ vọng* lớn nhất của lợi nhuận, nếu bạn chọn tập hợp $k$ ngày một cách tối ưu và sau đó đưa ra các quyết định giao dịch một cách tối ưu vào mỗi ngày trong $n$ ngày.

*Giá trị kỳ vọng là giá trị trung bình, có trọng số theo xác suất, của một biến ngẫu nhiên. Về mặt trực giác, đó là kết quả bạn mong đợi trung bình khi lặp lại một phép thử ngẫu nhiên nhiều lần.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), lần lượt biểu thị số ngày và số lượng mức giá mà bạn có thể biết ngay lập tức.

$n$ dòng tiếp theo mô tả các khoảng giá; dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i < b_i \le 10^6$).

Kết quả

In ra một số thực – giá trị kỳ vọng lớn nhất có thể của lợi nhuận sau $n$ ngày.

Sai số tương đối hoặc tuyệt đối cho phép là $10^{-6}$. Nghĩa là, nếu bạn in ra $x$ và kết quả chính xác đúng là $y$, thì điều kiện $|x - y| \le 10^{-6} \cdot \max(1, y)$ phải được thỏa mãn. Bạn có thể in tối đa $20$ chữ số sau dấu thập phân.

Ví dụ

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

Ghi chú

Ở test đầu tiên, ta có $k = 0$, nên mỗi mức giá đều được biết vào đầu ngày của nó. Tồn tại một chiến lược tối ưu là mua căn hộ vào ngày $1$ hoặc $2$ với chi phí kỳ vọng là $17.5$, sau đó bán nó vào ngày $3$ hoặc $4$ với thu nhập kỳ vọng là $46.25$. Lợi nhuận kỳ vọng là $46.25 - 17.5 = 28.75$.

Ở test thứ hai, ta có $k = 1$ và lựa chọn tối ưu là ngày $4$, vì vậy ta biết ngay lập tức một số thực $c_4$ thuộc đoạn $[30, 60]$. Lợi nhuận kỳ vọng là $31\frac{7}{18}$ với các quyết định giao dịch tối ưu.

Ở test thứ ba, lựa chọn tối ưu cho tập hợp $k$ ngày là $\{2, 3, 6\}$. Ta biết ngay lập tức các mức giá $c_2$, $c_3$ và $c_6$.