题目背景

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)$ 的水，混合后温度为：

说明

本题数据采用 SvRan 生成，仅用时 $3\min$。