題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

孫執行長任職於美味蛋糕股份有限公司，因為今年財報不如預期股東寄了公開信呼應公司能刪減成本，孫執行長決定要讓公司一些夥伴走自己的路。
孫執行長列出 $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, · · · , y_n$ 來表示一個小組所選擇的目標，有選擇第 $i$ 個公司目標則 $y_i = 1$，否則 $y_i = 0$。$AI$ 定義裁指數為：

孫執行長決定把所有小組的裁指數排名，如果一個人所屬於裁指數前 $k$ 大的小組就予以開除。想請你幫忙孫執行長找出排序後第 $k$ 大的裁指數。

例如： $n = 3$ 而 $k = 4,w_1 = 5, w_2 = −2, w_3 = 3$ ，會有 $\frac{3(3 + 1)}{2} = 6$ 個小組，每個小組的裁指數如下表 :

裁指數排序後為 $−2,\frac{1}{2},\frac{3}{2}, 3, 4, 5$ ，並且第 $4$ 大為 $\frac{3}{2}$ 。（備註：如果裁指數排名第 $k$ 大和第 $k + 1$ 大的裁指數相等，那孫執行長會另外想方法決定裁員名單，不需替他擔心）

測資限制

• $1 ≤ n ≤ 2 × 10^5$。
• $1 ≤ k ≤ \frac{n(n + 1)}{2}$。
• $−10^9 ≤ w_i ≤ 10^9$。
• $n, k, w_i$ 都是整數。