「Wdsr-2」间歇泉

**Problem Number:** $\textit{08}$

有一个间歇泉，冒出了 $n$ 杯水，由于一些原因，每杯水的温度、体积不同。第 $i$ 杯水的温度为 $c_i$，体积为 $a_i$。 现在混合任意**两**杯水，每混合两杯水都会得到一个新的温度值，求可能得到的第 $k$ 高的温度值（不计热量损失）。 **你的答案建议至少保留小数点后 $\bm3$ 位（与标准答案之差在 $\bm{10^{-2}}$ 以内即视为通过）。**

第一行一个数 $n,k$，意义如题述。 接下来 $n$ 行，每行两个数 $a_i,c_i$。

一行一个实数，表示混合后的水的第 $k$ 高温度。

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

4.500

#### 样例 1 说明 第 $1$ 和第 $5$ 杯水混合，得到 $4.5$ 的温度值。可以发现，这是可能得到的最高水温。 #### 样例 2 见题目附件中 $\textbf{\textit{pour2.in/pour2.ans}}$。 #### 数据规模与约定 **本题采用捆绑测试。** - $\textbf{Subtask 1}\text{ (10 pts)}$：$1\le n\le 10$。 - $\textbf{Subtask 2}\text{ (40 pts)}$：保证 $k=1$。 - $\textbf{Subtask 3}\text{ (50 pts)}$：无特殊限制。 - $\textbf{Subtask 4}\text{ (0 pts)}$：Hack 数据。 对于 $100\%$ 的数据，有 $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$。 子任务 2/3/4 时限 $\text{2 s}$，子任务 1 时限 $\text{1 s}$。 #### 前置知识 对于两杯体积、温度分别为 $(a_i,c_i),(a_j,c_j)$ 的水，混合后温度为： $$ T=\dfrac{a_ic_i+a_jc_j}{a_i+a_j} $$ #### 说明 本题数据采用 [SvRan](https://github.com/Sept0913/SvRan) 生成，仅用时 $3\min$。