การเก็งกำไรในตลาดอสังหาริมทรัพย์เป็นงานที่เครียดและมีรายได้ไม่แน่นอน มันจะช่วยได้ไหมถ้าคุณได้รับเงินกู้ก้อนโตจากพ่อแม่และสามารถคาดการณ์ราคาห้องชุดในวันที่เลือกได้อย่างแม่นยำ?

คุณเริ่มต้นโดยไม่มีห้องชุด แต่ยอดเงินในธนาคารของคุณคือ $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$ ทันที