题目描述

孫執行長任職於美味蛋糕股份有限公司，因為今年財報不如預期股東寄了公開信呼應公司能刪減成本，孫執行長決定要讓公司一些夥伴走自己的路。

孫執行長列出 $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$
	$1$	$0$	$(0-2+0)/(0+1+0) = -2$
		$1$	$(0-2+3)/(0+1+1) = \frac{1}{2}$
$1$	$0$	$0$	$(5+0+0)/(1+0+0) = 5$
		$1$	$(5+0+3)/(1+0+1) = 4$
	$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$ 必須互質。

3 4
5 -2 3

3
2

3 3
5 -2 3

3
1

9 45
5 -1 2 -3 6 -9 7 3 2

-9
1

提示

測資限制

• $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		$n \le 10^4$ 且 $k \le 2\times 10^5$
3		$n \le 10^4$
4	$40$	$k \le 2\times 10^5$
5	$14$	$-100 \le w_i \le 100$
6	$31$	無額外限制