[R13D]支架 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。

一个支架需要用两根木棍来制作，用长度分别为 $x$ 和 $y$ 的两根木棍制作的支架可以摆放任何重量不超过 $x\times y$ 的物品，但是只能摆放一件。

校长计划购买 $m$ 个重量一样的艺术品放在校园中，他请你制作 $m$ 个支架，把每个艺术品分别摆放在一个支架上。

请你告诉他购买的单个艺术品的重量最大是多少。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示木棍数量和艺术品的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每根木棍的长度。

输出格式

输出一个整数表示单个艺术品重量的最大值。

样例

样例输入 #1

6 2
3 5 2 4 2 7

样例输出 #1

20

样例解释 #1

可以用第 $1$ 根木棍和第 $6$ 根木棍制作能摆放重量不超过 $3\times 7=21$ 艺术品的支架，再用第 $2$ 根木棍和第 $4$ 根木棍制作能摆放重量不超过 $5\times 4=20$ 艺术品的支架。

数据规模

对于 $50\%$ 的数据，$n\leq 3000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq m\leq \lfloor\frac{n}{2}\rfloor$，$1\leq a_i\leq 10^5$。