Description

孙执行官任职于美味蛋糕股份有限公司，由于今年财报未达预期，股东寄了公开信呼吁公司削减成本，孙执行官决定让公司部分伙伴"走自己的路"。

孙执行官列出 $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)=0.5$
$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)=1.5$

裁减指数排序后为 $-2, 0.5, 1.5, 3, 4, 5$，第 $4$ 大的值为 $1.5$。（备注：若第 $k$ 大与第 $k+1$ 大的裁减指数相同，孙执行官会另行决定裁员名单，不需要替他担心）

Input Format

$n$ $k$
$w_1$ $w_2$ $\cdots$ $w_n$

• $n$ 表示公司目标数量
• $k$ 表示需要查询的排名
• $w_i$ 表示第 $i$ 个目标的权重

Output Format

$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

Hint

测试数据限制

• $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		$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	无额外限制