Description

There is a geyser that produced $n$ cups of water. For some reasons, each cup has a different temperature and volume. The temperature of the $i$-th cup is $c_i$, and the volume is $a_i$.

Now mix any two cups of water. Each time you mix two cups, you will get a new temperature value. Find the $k$-th highest possible temperature value (ignoring heat loss).

It is recommended that your answer keep at least $\bm 3$ digits after the decimal point (it will be accepted if the difference from the standard answer is within $\bm{10^{-2}}$).

Input Format

The first line contains two integers $n, k$, as described above.

The next $n$ lines each contain two numbers $a_i, c_i$.

Output Format

Output one real number, representing the $k$-th highest temperature after mixing.

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

4.500

Hint

Explanation for Sample 1

Mixing the $1$-st and the $5$-th cups gives a temperature value of $4.5$. It can be seen that this is the highest possible water temperature.

Sample 2

See the attached files $\textbf{\textit{pour2.in/pour2.ans}}$.

Constraints and Notes

This problem uses bundled testdata.

• $\textbf{Subtask 1}\text{ (10 pts)}$: $1\le n\le 10$.
• $\textbf{Subtask 2}\text{ (40 pts)}$: guaranteed $k=1$.
• $\textbf{Subtask 3}\text{ (50 pts)}$: no special restrictions.
• $\textbf{Subtask 4}\text{ (0 pts)}$: hack testdata.

For $100\%$ of the data: $1\le n\le 10^5$, $1\le k\le \dfrac{n \times (n - 1)}{2}$, $1\le a_i,c_i\le 10^9$.

The time limit is $\text{2 s}$ for Subtasks 2/3/4, and $\text{1 s}$ for Subtask 1.

Prerequisite Knowledge

For two cups of water with volume and temperature $(a_i,c_i),(a_j,c_j)$, the temperature after mixing is:

Note

The testdata of this problem is generated using SvRan, taking only $3\min$.

Translated by ChatGPT 5