Thu thập

Marisa nổi tiếng thích nhặt nhạnh. Trước mặt cô đang có \(n\) món đồ, món đồ thứ \(i\) có cân nặng là \(w_i\) và giá trị là \(v_i\). Cô rất muốn lấy hết chúng về nhà, nhưng chúng lại quá nặng, nên cô quyết định chỉ lấy đúng \(k\) món.

Nếu lấy \(k\) món đồ, giá trị của chúng là:

Hãy giúp cô chọn đồ sao cho giá trị đạt được là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le k \le n \le 10^5\)).

• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(v_i, w_i\) (\(1 \le v_i, w_i \le 10^9\)).

Output

In ra một số thực là giá trị lớn nhất có thể đạt được. Đáp án được coi là chính xác khi chênh lệch với đáp án đúng không quá \(10^{-3}\).

Example

Input:

5 3
1 3
2 2
2 5
4 2
1 4

Output:

1.0000000000