Спекуляція на ринку нерухомості — стресова робота з нестабільним заробітком. Чи допомогло б вам, якби ви отримали величезний кредит від батьків і могли точно передбачати ціни на квартири у вибрані дні?

Спочатку у вас немає квартири, але ваш банківський баланс становить $10^{100}$. Оскільки у вас немає ліцензії рієлтора, ви можете володіти щонайбільше однією квартирою одночасно. Ви вже пригледіли конкретну квартиру в хорошому місці, і саме її ви можете купувати, а потім продавати, можливо, кілька разів.

Галузевий портал MyHouse опублікував прогнозовані інтервали $[a_i, b_i]$ (де $a_i < b_i$) ціни цієї квартири на наступні $n$ днів. Ціна квартири в $i$-й день — це випадкове дійсне число $c_i$, вибране рівномірно випадково з відрізка $[a_i, b_i]$. За замовчуванням ви дізнаєтеся ціну $c_i$ на початку $i$-го дня. Після цього ви повинні вирішити, чи здійснювати угоду. Якщо ви володієте квартирою, ви можете продати її за $c_i$, а якщо не володієте — купити за $c_i$.

Лише сьогодні (до початку першого дня) портал MyHouse дозволяє новим користувачам дізнатися точні ціни $c_i$ для вибраної множини з $k$ днів. Тобто зараз ви вибираєте множину з $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$, тож ми одразу дізнаємося дійсне число $c_4$ з відрізка $[30, 60]$. Очікуваний прибуток за оптимальних рішень щодо угод становить $31\frac{7}{18}$.

У третьому тесті оптимальним вибором множини з $k$ днів є $\{2, 3, 6\}$. Ми одразу дізнаємося ціни $c_2$, $c_3$ та $c_6$.