不動産市場での投機は、収入が不安定でストレスの多い仕事です。もし両親から巨額の融資を受けられ、さらに選んだ日のマンション価格を正確に予測できるとしたら、少しは楽になるでしょうか？

あなたは最初マンションを所有していませんが、銀行口座の残高は $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$ を即座に知ることができます。