AT_abc149_e [ABC149E] Handshake

题目描述

高桥作为特邀嘉宾参加了一个派对。派对上有 $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 \lt q \leq M)$ 满足 $(x_p,y_p)=(x_q,y_q)$ 。

请问握手 $M$ 次后可能的最大快乐值是多少？

输入格式

输入内容由标准输入提供，格式如下：

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

输出格式

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

样例 1

输入

5 3
10 14 19 34 33

输出

202

样例 2

输入

9 14
1 3 5 110 24 21 34 5 3

输出

1837

样例 3

输入

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$
• 所有输入均为整数。

样例解释

对于样例 #1：

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

• 第一次握手时，高桥握住了客人 $4$ 的左手和客人 $4$ 的右手。
• 第二次握手时，高桥握住了客人 $4$ 的左手和客人 $5$ 的右手。
• 第三次握手时，高桥握住了客人 $5$ 的左手和客人 $4$ 的右手。

这样，我们将拥有 $(34+34)+(34+33)+(33+34)=202$ 的幸福值。

我们无法获得 $203$ 及以上的幸福值，所以答案是 $202$ 。