握手

题目描述

高桥君作为特别嘉宾来到了一场派对。 派对上有 $N$ 位普通来宾，普通来宾 $i$（$1 \leq i \leq N$）的力量为 $A_i$。

高桥君决定通过进行 $M$ 次握手来提高整个派对的幸福度（握手开始前幸福度为 $0$）。 握手按以下步骤进行：

• 高桥君决定用左手握手的（普通）来宾 $x$ 和用右手握手的来宾 $y$（两只手握同一个来宾的手也可以）。
• 高桥君实际握这两只手，幸福度提高 $A_x+A_y$。

但是，不能进行两次以上完全相同的握手。严格地说，必须满足以下条件：

• 设第 $k$ 次握手中，左手握来宾 $x_k$、右手握来宾 $y_k$。此时，不存在满足 $(x_p,y_p)=(x_q,y_q)$ 的 $p,q$（$1 \leq p \lt q \leq M$）。

进行 $M$ 次握手后，最终幸福度最大可以是多少呢？

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $A_2$ $...$ $A_N$

输出格式

输出进行 $M$ 次握手后的最终幸福度的最大值。

样例

5 3
10 14 19 34 33

202

例如：

• 第 $1$ 次握手用左手握来宾 $4$、右手握来宾 $4$，
• 第 $2$ 次握手用左手握来宾 $4$、右手握来宾 $5$，
• 第 $3$ 次握手用左手握来宾 $5$、右手握来宾 $4$，

这样可以将幸福度提高到 $(34+34)+(34+33)+(33+34)=202$。

无法将幸福度提高到 $203$ 以上，因此答案是 $202$。

9 14
1 3 5 110 24 21 34 5 3

1837

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

8128170

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq M \leq N^2$
• $1 \leq A_i \leq 10^5$
• 输入均为整数。