在房地產市場中進行投機是一項壓力龐大且收入不穩定的工作。如果你能從父母那裡獲得一筆巨額貸款，並且能夠精確預測特定幾天的公寓價格，這會有幫助嗎？

你一開始沒有公寓，但你的銀行帳戶餘額為 $10^{100}$。由於你沒有房地產經紀人執照，你同時最多只能擁有一間公寓。你已經看中了一間地段良好的特定公寓，而那就是你可以買入再賣出（可能多次）的公寓。

產業入口網站 MyHouse 公佈了未來 $n$ 天該公寓價格的預測區間 $[a_i, b_i]$（滿足 $a_i < b_i$）。第 $i$ 天的公寓價格是從區間 $[a_i, b_i]$ 中均勻隨機選取的一個隨機實數 $c_i$。預設情況下，你會在第 $i$ 天開始時得知價格 $c_i$。接著你必須決定是否進行交易。如果你擁有該公寓，你可以以 $c_i$ 的價格將其賣出；如果你沒有擁有該公寓，你可以以 $c_i$ 的價格將其買入。

唯有今天（在第一天開始之前），MyHouse 入口網站允許新用戶預先得知所選 $k$ 天集合的確切價格 $c_i$。也就是說，你現在選擇一個包含 $k$ 天的集合並得知這些天的價格，而對於其餘的 $n - k$ 天，你將在每一天開始時得知當天的價格。

在 $n$ 天之後，你必須以沒有公寓的狀態結束；你的利潤是最終銀行餘額與初始銀行餘額之間的差額。若你以最佳方式選擇這 $k$ 天的集合，並在全部 $n$ 天中的每一天都做出最佳的交易決策，請計算利潤的最大期望值*。

*隨機變數的期望值是按機率加權的平均值。直觀地說，它是多次重複隨機實驗時平均預期會得到的結果。

輸入格式

第一行包含兩個整數 $n$ 和 $k$（$0 \le k \le n \le 300\,000$；$1 \le n$），分別代表天數以及你可以立即得知的價格數量。

接下來的 $n$ 行描述價格區間；第 $i$ 行包含兩個整數 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le 10^6$）。

輸出格式

輸出一個實數 —— $n$ 天後利潤的最大可能期望值。

可接受的相對或絕對誤差為 $10^{-6}$。也就是說，如果你輸出 $x$ 且正確的精確結果為 $y$，則必須滿足 $|x - y| \le 10^{-6} \cdot \max(1, y)$。你可以在小數點後輸出最多 $20$ 位數字。

範例

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

提示

在第一個測試中，我們有 $k = 0$，因此每個價格都是在當天開始時才得知的。存在一種最佳策略：在第 $1$ 天或第 $2$ 天以 $17.5$ 的期望成本買入公寓，然後在第 $3$ 天或第 $4$ 天以 $46.25$ 的期望收入將其賣出。期望利潤為 $46.25 - 17.5 = 28.75$。

在第二個測試中，我們有 $k = 1$，我們應該最佳地選擇第 $4$ 天，因此我們立即得知區間 $[30, 60]$ 中的一個實數 $c_4$。在最佳交易決策下，期望利潤為 $31\frac{7}{18}$。

在第三個測試中，這 $k$ 天集合的最佳選擇是 $\{2, 3, 6\}$。我們會立即得知價格 $c_2$、$c_3$ 和 $c_6$。