题目描述

高橋君は、あるパーティに特別ゲストとしてやってきました。 そこには一般ゲストが $N$ 人おり、一般ゲスト $i$ $(1\ \leq\ i\ \leq\ N)$ の パワー は $A_i$ です。

高橋君は 握手 を $M$ 回行うことで、パーティ全体の 幸福度 を上げることにしました(握手開始前の幸福度を $0$ とします)。 握手は、以下の手順によって行われます。

• 高橋君が左手で手を握る (一般) ゲスト $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$ 回の握手を行った後、最終的な幸福度は最大でいくらにできるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$M$ 回の握手を行った後の最終的な幸福度の最大値を出力せよ。

题目大意

题目描述

Takahashi 作为特殊嘉宾参加一个晚会 , 晚会上还有 N 个非特殊嘉宾 , 第 i 个特殊嘉宾有 A_i 的欢乐值.晚会目前的欢乐值是 0 .
Takahashi 想跟非特殊嘉宾握 M 次手来提高晚会的欢乐值.每一次握手可以被描述为以下的操作:

1. Takahashi 选择两个非特殊嘉宾 x 和 y
2. Takahashi 用左手和 x 握手 , 用右手和 y 握手 , 晚会的欢乐值增加 A_x + A_y .

然而 , Takahashi 不能以同一种握手方式握两次手.也就是说 , Takahashi 的 M 次握手必须满足以下条件:

• 假设在第 k 次握手中 , Takashi 握了非特殊嘉宾 x_k 的左手和 y_k 的右手 , 则没有一组 p , q ( 1 ≤ p < q ≤ M) 可以满足 ( x_p , y_p ) = ( x_q , y_q ) .

请问:在 M 次握手后 , 晚会的欢乐值最大是多少 ?

输入格式

第一行: N , M
第二行: A_1 , A_2 , ··· , A_N

输出格式

一行 , 最大的欢乐值

翻译者的个人中心
翻译者的博客

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$
• 入力は全て整数である。

Sample Explanation 1

例えば、 - $1$ 回目の握手で左手でゲスト $4$、右手でゲスト $4$ と握手し、 - $2$ 回目の握手で左手でゲスト $4$、右手でゲスト $5$ と握手し、 - $3$ 回目の握手で左手でゲスト $5$、右手でゲスト $4$ と握手する ことで、幸福度を $(34+34)+(34+33)+(33+34)=202$ とすることができます。 幸福度を $203$ 以上にはできないので、答えは $202$ となります。