喺房地產市場炒樓係一份壓力好大而且收入唔穩定嘅工作。如果你可以問父母借一大筆錢，又可以準確預測指定日數嘅樓價，咁會唔會有幫助呢？

你一開始冇單位，但係你嘅銀行結餘有 $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$。