题目描述

Takahashi has come to a party as a special guest. There are $N$ ordinary guests at the party. The $i$-th ordinary guest has a power of $A_i$.

Takahashi has decided to perform $M$ handshakes to increase the happiness of the party (let the current happiness be $0$). A handshake will be performed as follows:

• Takahashi chooses one (ordinary) guest $x$ for his left hand and another guest $y$ for his right hand ($x$ and $y$ can be the same).
• Then, he shakes the left hand of Guest $x$ and the right hand of Guest $y$ simultaneously to increase the happiness by $A_x+A_y$.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

• Assume that, in the $k$-th handshake, Takahashi shakes the left hand of Guest $x_k$ and the right hand of Guest $y_k$. Then, there is no pair $p, q$ $(1 \leq p \lt q \leq M)$ such that $(x_p,y_p)=(x_q,y_q)$.

What is the maximum possible happiness after $M$ handshakes?

高桥作为特邀嘉宾参加了一个聚会。派对上有 $N$ 位普通客人。

高桥决定用 $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

样例输入 #1

5 3
10 14 19 34 33

样例输出 #1

202

样例 #2

样例输入 #2

9 14
1 3 5 110 24 21 34 5 3

样例输出 #2

1837

样例 #3

样例输入 #3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

样例输出 #3

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$ 。