P11849 [TOIP 2023] 裁员风暴

孙执行官任职于美味蛋糕股份有限公司，由于今年财报未达预期，股东寄了公开信呼吁公司削减成本，孙执行官决定让公司部分伙伴"走自己的路"。 孙执行官列出 $n$ 个公司目标，并请员工们各自从 $n$ 个公司目标挑选 $1$ 个或 $2$ 个他们认为最重要的目标。做出相同选择的员工会被分类到同一个**小组**。已知每种可能的目标组合都至少有一位员工选择，可以计算出恰好选择 $1$ 个目标的小组有 $n$ 组，恰好选择 $2$ 个目标的小组有 $\frac{n(n-1)}{2}$ 组，合计共有 $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$ 个小组。 通过 AI 大数据分析，每个公司目标都被 AI 赋予一个权重，这里用 $w_i$ 表示第 $i$ 个公司目标的权重。我们可以用一个 $01$-序列 $y$：$y_1, y_2, \cdots, y_n$ 来表示一个小组所选择的目标（选择第 $i$ 个目标则 $y_i = 1$，否则 $y_i = 0$）。AI 定义**裁减指数**为： $$\left( \dfrac{\displaystyle \sum_{i=1}^{n}w_i\times y_i}{\displaystyle \sum_{j=1}^{n} y_j} \right)$$ 孙执行官决定将所有小组的裁减指数排名，属于**裁减指数前 $k$ 大小组**的员工将被开除。 请你帮助孙执行官找出排序后第 $k$ 大的裁减指数。 例如：当 $n=3$，$k=4$，$w_1=5, w_2=-2, w_3=3$ 时，共有 $\dfrac{3(3+1)}{2} = 6$ 个小组，各小组裁减指数如下表： |$y_1$|$y_2$|$y_3$|裁减指数 | |:---:|:---:|:---:|:---------------------| | $0$ | $0$ | $1$ |$(0+0+3)/(0+0+1) = 3$| | $0$ | $1$ | $0$ |$(0-2+0)/(0+1+0) =-2$| | $0$ | $1$ | $1$ |$(0-2+3)/(0+1+1)=0.5$| | $1$ | $0$ | $0$ |$(5+0+0)/(1+0+0) = 5$| | $1$ | $0$ | $1$ |$(5+0+3)/(1+0+1) = 4$| | $1$ | $1$ | $0$ |$(5-2+0)/(1+1+0)=1.5$| 裁减指数排序后为 $-2, 0.5, 1.5, 3, 4, 5$，第 $4$ 大的值为 $1.5$。（备注：若第 $k$ 大与第 $k+1$ 大的裁减指数相同，孙执行官会另行决定裁员名单，不需要替他担心）

> $n$ $k$ > $w_1$ $w_2$ $\cdots$ $w_n$ * $n$ 表示公司目标数量 * $k$ 表示需要查询的排名 * $w_i$ 表示第 $i$ 个目标的权重

> $p$ > $q$ * $\dfrac{p}{q}$ 表示第 $k$ 大的裁减指数 * $p$ 必须为整数 * $q$ 必须为正整数 * $|p|$ 与 $q$ 必须互质

### 测试数据限制 * $1 \le n \le 2\times 10^5$ * $1 \le k \le \dfrac{n(n+1)}{2}$ * $-{10}^9 \le w_i \le {10}^9$ * 所有输入均为整数 ### 评分说明 本题共有六个子任务，限制条件如下。每个子任务需通过全部测试数据方可得分。 | 子任务 | 分数 | 额外限制 | | :----: | :--: | --------------------------- | | 1 | 5 | $n \le 20$ | | 2 | 5 | $n \le 10^4$ 且 $k \le 2\times 10^5$ | | 3 | 5 | $n \le 10^4$ | | 4 | 40 | $k \le 2\times 10^5$ | | 5 | 14 | $-100 \le w_i \le 100$ | | 6 | 31 | 无额外限制 |