ספקולציות בשוק הנדל"ן הן עבודה מלחיצה עם הכנסות לא יציבות. האם זה היה עוזר אילו קיבלת הלוואה עצומה מההורים שלך ויכולת לחזות במדויק את מחירי הדירות בימים נבחרים?

אתה מתחיל ללא דירה, אך יתרת הבנק שלך היא $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$.