题目描述

We have $N$ integers $A_1, A_2, ..., A_N$.

There are $\frac{N(N-1)}{2}$ ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the $K$-th number in that list?

我们有 $N$ 个整数 $A_1, A_2, ..., A_N$ 。

有 $\frac{N(N-1)}{2}$ 种方法可以选择其中的两个并组成一对。如果我们计算每一对的乘积，并将结果按升序排序，那么列表中的第 $K$ 个数字是多少？

输入格式

输入内容按以下格式标准输入：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

打印答案。

样例 #1

样例输入 #1

4 3
3 3 -4 -2

样例输出 #1

-6

样例 #2

样例输入 #2

10 40
5 4 3 2 -1 0 0 0 0 0

样例输出 #2

6

样例 #3

样例输入 #3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

样例输出 #3

448283280358331064

说明

数据规模与约定

• 输入值均为整数
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq \frac{N(N-1)}{2}$
• $-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)$

样例 $1$ 解释

有六种方法可以组成一对。它们的乘积是 $9$ 、 $-12$ 、 $-6$ 、 $-12$ 、 $-6$ 、 $8$ 。

将这些数字按升序排列，我们得到 $-12$ ， $-12$ ， $-6$ ， $-6$ ， $8$ ， $9$ 。这个列表中的第三个数字是 $-6$ 。