Handshake

题目描述

Takahashi 作为特别嘉宾来到了一个派对。 派对上有 $N$ 位普通嘉宾。第 $i$ 位普通嘉宾的力量为 $A_i$。 Takahashi 决定进行 $M$ 次握手以增加派对的快乐值（初始快乐值记为 $0$）。 一次握手按如下方式进行：

Takahashi 为他的左手选择一位（普通）嘉宾 $x$，为他的右手选择另一位嘉宾 $y$（$x$ 和 $y$ 可以相同）。 然后，他同时和嘉宾 $x$ 的左手与嘉宾 $y$ 的右手握手，使快乐值增加 $A_x+A_y$。

但是，Takahashi 不应当重复进行相同的握手。形式化地，必须满足以下条件：

假设在第 $k$ 次握手中，Takahashi 握的是第 $x_k$ 位嘉宾的左手和第 $y_k$ 位嘉宾的右手。那么，不存在一对 $p, q$ (1 \leq p < q \leq M) 使得 $(x_p,y_p)=(x_q,y_q)$。

进行 $M$ 次握手后，快乐值的最大可能值是多少？

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出进行 $M$ 次握手后快乐值的最大可能值。

5 3
10 14 19 34 33

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$ 输入中的所有数值均为整数。我们假设 Takahashi 进行了如下握手：

第一次握手，Takahashi 握第 $4$ 位嘉宾的左手和第 $4$ 位嘉宾的右手。 第二次握手，Takahashi 握第 $4$ 位嘉宾的左手和第 $5$ 位嘉宾的右手。 第三次握手，Takahashi 握第 $5$ 位嘉宾的左手和第 $4$ 位嘉宾的右手。

那么，快乐值为 $(34+34)+(34+33)+(33+34)=202$。 我们不能得到 $203$ 或更大的快乐值，所以答案为 $202$.

标签: AtCoder|abc149E

来源

AtCoder|abc149E