题目描述

高桥作为特别嘉宾参加了一个聚会。聚会上有 $N$ 位普通的客人。第 $i$ 位普通客人具有 $A_i$ 的 力量。

高桥决定进行 $M$ 次握手来增加聚会的 快乐度（当前的快乐度为 $0$）。握手的过程如下：

• 高桥选择一位（普通）客人 $x$ 作为他的左手，另一位客人 $y$ 作为他的右手（$x$ 和 $y$ 可以是同一位客人）。
• 然后，他同时与客人 $x$ 左手握手和客人 $y$ 右手握手，将快乐度增加 $A_x+A_y$。

然而，高桥不能重复进行相同的握手。形式化地说，以下条件必须满足：

• 假设在第 $k$ 次握手中，高桥与客人 $x_k$ 左手握手和客人 $y_k$ 右手握手。那么，不存在对 $(x_p,y_p)=(x_q,y_q)$ 的一对 $p, q$ $(1 \\leq p < q \\leq M)$。

$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$ 次握手后能够达到的最大快乐度。

示例输入 1

5 3
10 14 19 34 33

示例输出 1

202

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

• 在第一次握手中，高桥与客人 $4$ 左手握手和客人 $4$ 右手握手。
• 在第二次握手中，高桥与客人 $4$ 左手握手和客人 $5$ 右手握手。
• 在第三次握手中，高桥与客人 $5$ 左手握手和客人 $4$ 右手握手。

然后，我们将得到 $(34+34)+(34+33)+(33+34)=202$ 的快乐度。

我们无法达到 $203$ 或更高的快乐度，因此答案是 $202$。

示例输入 2

9 14
1 3 5 110 24 21 34 5 3

示例输出 2

1837

示例输入 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

示例输出 3

8128170