부동산 시장에서의 투기는 수입이 불안정하고 스트레스가 많은 일입니다. 부모님께 거액의 대출을 받고 선택한 날짜의 아파트 가격을 정확히 예측할 수 있다면 도움이 될까요?

당신은 아파트 없이 시작하지만, 은행 잔고는 $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$을 즉시 알게 됩니다.