AT_abc149_e [ABC149E] Handshake

[problemUrl]: https://atcoder.jp/contests/abc149/tasks/abc149_e 高橋君は、あるパーティに特別ゲストとしてやってきました。 そこには一般ゲストが $ 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\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

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

### 制約 - $ 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 $ となります。