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) = \frac{1}{2}$| | $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) = \frac{3}{2}$| 裁指數排序後為 $-2, \frac{1}{2}, \frac{3}{2}, 3, 4, 5$，並且第 $4$ 大為 $\frac{3}{2}$。（備註：如果裁指數排名第 $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$。 * $n, k, w_i$ 都是整數。 ### 評分說明 本題共有六組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----------------: | ------------------------------------ | | 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$ | 無額外限制 |