E - 握手

分数：$500$ 点

问题描述

高桥作为特殊嘉宾来到了一场派对上。 派对上有 $N$ 位普通嘉宾。第 $i$ 位普通嘉宾的力量为 $A_i$。

高桥决定进行 $M$ 次握手来增加派对的幸福感（当前的幸福感为 $0$）。 握手的过程如下：

• 高桥选择一位（普通）嘉宾 $x$ 为他的左手，另一位嘉宾 $y$ 为他的右手（$x$ 和 $y$ 可以相同）。
• 然后，他同时握住嘉宾 $x$ 的左手和嘉宾 $y$ 的右手，使幸福感增加 $A_x+A_y$。

然而，高桥不能进行相同的握手超过一次。形式上讲，必须满足以下条件：

• 假设在第 $k$ 次握手中，高桥握住了嘉宾 $x_k$ 的左手和嘉宾 $y_k$ 的右手。那么，不能存在一对儿的 $p, q$ $(1 \leq p < q \leq M)$，满足 $(x_p,y_p)=(x_q,y_q)$。

在进行 $M$ 次握手后，最大的幸福感是多少？

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq N^2$
• $1 \leq A_i \leq 10^5$
• 输入中所有的值都是整数。

输入

输入数据以以下格式从标准输入中给出：

$N$ $M$

$A_1$ $A_2$ $...$ $A_N$

输出

输出 $M$ 次握手后可能的最大幸福感。

5 3
10 14 19 34 33

202

假设高桥进行了以下握手：

• 在第一次握手中，高桥握住了嘉宾 $4$ 的左手和嘉宾 $4$ 的右手。
• 在第二次握手中，高桥握住了嘉宾 $4$ 的左手和嘉宾 $5$ 的右手。
• 在第三次握手中，高桥握住了嘉宾 $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