Yunzi có ~n~ dải đất nằm trên một đường thẳng. Dải thứ ~i~ là đoạn ~[l_i, r_i]~. Các dải đôi một không giao nhau và được cho theo thứ tự tăng dần của ~l_i~.

Cô ấy muốn trồng đúng ~k~ cây. Mỗi cây được trồng tại một vị trí thực bất kỳ thuộc một dải đất nào đó, và nhiều cây có thể được trồng trên cùng một dải.

Yunzi muốn các cây càng thưa càng tốt. Hãy tìm giá trị lớn nhất có thể của khoảng cách giữa hai cây gần nhau nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~ và ~r_i~.

Kết quả

In ra khoảng cách lớn nhất có thể giữa hai cây gần nhau nhất.

Đáp án của bạn được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-6}~. Nói cách khác, nếu đáp án của bạn là ~x~ và đáp án đúng là ~y~ thì bạn được chấp nhận khi ~|x - y| < 10^{-6}~.

Ví dụ

Đầu vào:

2 4
0 2
3 10

Đầu ra:

3.333333

Giải thích: Trồng bốn cây tại các vị trí ~0~, ~\dfrac{10}{3}~, ~\dfrac{20}{3}~, ~10~. Cây thứ hai và thứ ba nằm trên dải ~[3, 10]~. Hai cây gần nhau nhất cách nhau ~\dfrac{10}{3} \approx 3.333333~. Không có cách trồng nào cho khoảng cách nhỏ nhất lớn hơn.

Giới hạn

• ~1 \le n \le 10^5~
• ~2 \le k \le 10^5~
• ~0 \le l_i \le r_i \le 10^9~
• ~r_i < l_{i+1}~ với mọi ~1 \le i < n~

Đáp án hầu như không phải số nguyên, vì vậy tìm kiếm nhị phân trên tập số nguyên sẽ cho kết quả sai. Hãy chặt nhị phân trên miền số thực và chú ý sai số ~10^{-6}~ chặt hơn nhiều so với các bài trước.