Жылжымайтын мүлік нарығындағы алыпсатарлық — табысы тұрақсыз әрі күйзеліске толы жұмыс. Егер ата-анаңыздан қомақты несие алып, таңдалған күндердегі пәтер бағасын дәл болжай алсаңыз, бұл көмектесер ме еді?

Сіз басында пәтерсіз бастайсыз, бірақ банктік шотыңыздағы қалдық $10^{100}$ тең. Сізде риелтор лицензиясы болмағандықтан, бір уақытта ең көп дегенде бір ғана пәтерге иелік ете аласыз. Сіз жақсы жерде орналасқан белгілі бір пәтерді көздеп қойдыңыз, және дәл сол пәтерді бірнеше рет сатып алып, кейін сата аласыз.

MyHouse салалық порталы алдағы $n$ күнге пәтер бағасының болжамды $[a_i, b_i]$ аралықтарын ($a_i < b_i$) жариялады. $i$-ші күنگі пәтердің бағасы — $[a_i, b_i]$ кесіндісінен бірқалыпты кездейсоқ таңдалған кездейсоқ нақты сан $c_i$. Әдетте, сіз $c_i$ бағасын $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$ бағаларын бірден білеміз.