La spéculation sur le marché immobilier est un travail stressant aux revenus instables. Cela vous aiderait-il d'obtenir un prêt énorme de vos parents et de pouvoir prédire avec précision le prix des appartements à certains jours choisis ?

Vous commencez sans appartement, mais votre solde bancaire est de $10^{100}$. Comme vous n'avez pas de licence d'agent immobilier, vous ne pouvez posséder qu'un seul appartement à la fois au maximum. Vous avez déjà repéré un appartement spécifique bien situé, et c'est celui que vous pouvez acheter puis revendre, éventuellement plusieurs fois.

Le portail spécialisé MyHouse a publié des intervalles prévisionnels $[a_i, b_i]$ (avec $a_i < b_i$) du prix de l'appartement pour les $n$ prochains jours. Le prix de l'appartement le $i$-ème jour est un nombre réel aléatoire $c_i$ choisi uniformément au hasard dans l'intervalle $[a_i, b_i]$. Par défaut, vous apprenez le prix $c_i$ au début du $i$-ème jour. Vous devez alors décider si vous effectuez une transaction. Si vous possédez l'appartement, vous pouvez le vendre au prix $c_i$, et si vous ne le possédez pas, vous pouvez l'acheter au prix $c_i$.

Aujourd'hui seulement (avant le premier jour), le portail MyHouse permet aux nouveaux utilisateurs de connaître les prix exacts $c_i$ pour un ensemble choisi de $k$ jours. Autrement dit, vous choisissez maintenant un ensemble de $k$ jours et apprenez leurs prix, tandis que pour chacun des $n - k$ jours restants, vous apprendrez le prix au début de ce jour-là.

Après $n$ jours, vous devez terminer sans appartement ; votre profit est la différence entre votre solde bancaire final et votre solde initial. Déterminez l'espérance* maximale du profit, si vous choisissez de manière optimale l'ensemble de $k$ jours puis prenez de manière optimale les décisions de transaction lors de chacun des $n$ jours.

*L'espérance mathématique est la valeur moyenne, pondérée par les probabilités, d'une variable aléatoire. Intuitivement, c'est le résultat auquel on peut s'attendre en moyenne en répétant une expérience aléatoire un grand nombre de fois.

Entrée

La première ligne contient deux entiers $n$ et $k$ ($0 \le k \le n \le 300\,000$ ; $1 \le n$), représentant respectivement le nombre de jours et le nombre de prix que vous pouvez connaître immédiatement.

Les $n$ lignes suivantes décrivent les intervalles de prix ; la $i$-ème ligne contient deux entiers $a_i$ et $b_i$ ($1 \le a_i < b_i \le 10^6$).

Sortie

Affichez un nombre réel – l'espérance maximale possible du profit après $n$ jours.

L'erreur relative ou absolue acceptable est de $10^{-6}$. C'est-à-dire que si vous affichez $x$ et que le résultat exact est $y$, alors on doit avoir $|x - y| \le 10^{-6} \cdot \max(1, y)$. Vous pouvez afficher jusqu'à $20$ chiffres après la virgule.

Exemples

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

Dans le premier test, nous avons $k = 0$, donc chaque prix est appris au début de son jour. Il existe une stratégie optimale consistant à acheter l'appartement le jour $1$ ou $2$ pour un coût espéré de $17.5$, puis à le revendre le jour $3$ ou $4$ pour un revenu espéré de $46.25$. Le profit espéré est $46.25 - 17.5 = 28.75$.

Dans le deuxième test, nous avons $k = 1$ et il est optimal de choisir le jour $4$, ce qui nous permet d'apprendre immédiatement un nombre réel $c_4$ de l'intervalle $[30, 60]$. Le profit espéré est de $31\frac{7}{18}$ pour des décisions de transaction optimales.

Dans le troisième test, le choix optimal de l'ensemble de $k$ jours est $\{2, 3, 6\}$. Nous apprenons immédiatement les prix $c_2$, $c_3$ et $c_6$.