Спекуляция на рынке недвижимости — стрессовая работа с нестабильным доходом. Помогло бы вам, если бы вы получили огромный кредит от родителей и могли точно предсказывать цены на квартиры в выбранные дни?
Вначале у вас нет квартиры, но ваш банковский баланс равен $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$.