Speculation in the real estate market is stressful work with unstable earnings. Would it help if you got a huge loan from your parents and could precisely predict apartment prices on selected days?

You start without an apartment, but your bank balance is $10^{100}$. Since you lack a real estate agent license, you may own at most one apartment at a time. You have already spotted a specific apartment in a good location, and that is the one you may buy and then sell, possibly multiple times.

The industry portal MyHouse has published predicted intervals $[a_i, b_i]$ (with $a_i < b_i$) of the apartment's price for the next $n$ days. The price of the apartment on the $i$-th day is a random real number $c_i$ chosen uniformly at random from the interval $[a_i, b_i]$. By default, you learn the price $c_i$ at the beginning of the $i$-th day. You must then decide whether to make a transaction. If you own the apartment, you may sell it for $c_i$, and if you do not own it, you may buy it for $c_i$.

Only today (before the first day) the MyHouse portal allows new users to learn the exact prices $c_i$ for a chosen set of $k$ days. That is, you now choose a set of $k$ days and learn their prices, while for each of the remaining $n - k$ days you will learn the price at the beginning of that day.

After $n$ days you must end without an apartment; your profit is the difference between your final and initial bank balance. Determine the maximum expected value* of the profit, if you optimally choose the set of $k$ days and then optimally make transaction decisions on each of the $n$ days.

*The expected value is the average value, weighted by probability, of a random variable. Intuitively, it is the result you would expect on average when repeating a random experiment many times.

Input

The first line contains two integers $n$ and $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), representing respectively the number of days and the number of prices you may learn immediately.

The next $n$ lines describe price intervals; the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le 10^6$).

Output

Print one real number – the maximum possible expected value of the profit after $n$ days.

The acceptable relative or absolute error is $10^{-6}$. That is, if you print $x$ and the correct exact result is $y$, then it must hold that $|x - y| \le 10^{-6} \cdot \max(1, y)$. You may print up to $20$ digits after the decimal point.

Examples

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

Note

In the first test we have $k = 0$, so each price is learned at the beginning of its day. There exists an optimal strategy of buying the apartment on day $1$ or $2$ at an expected cost of $17.5$, and then selling it on day $3$ or $4$ with an expected income of $46.25$. The expected profit is $46.25 - 17.5 = 28.75$.

In the second test we have $k = 1$ and we should optimally choose day $4$, so we immediately learn a real number $c_4$ from the interval $[30, 60]$. The expected profit is $31\frac{7}{18}$ for optimal transaction decisions.

In the third test the optimal choice of the set of $k$ days is $\{2, 3, 6\}$. We immediately learn the prices $c_2$, $c_3$, and $c_6$.