← 返回题目列表

AtCoder · abc149_e

E. 握手

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

高桥作为特邀嘉宾参加了一个聚会。 有 N 聚会上的普通客人。的 i第一个普通客人有一个 电源 of A_i.

高桥决定表演 M 握手 增加 幸福 党的 (让现在的幸福 0)。 握手将按如下方式进行:

  • 高桥选择一名(普通)客人 x 为他的左手和另一位客人 y 为他的右手 (x 和 y 可以相同)。
  • 然后,他握了客人的左手 x 和客人的右手 y 同时增加幸福感 A_x+A_y.

但是,Takahashi 不应多次执行相同的握手。形式上,必须满足以下条件:

  • 假设,在 k第次握手,高桥与客人左手握手 x_k 和客人的右手 y_k。然后就没有配对了 p, q (1 \leq p < q \leq M) 这样 (x_p,y_p)=(x_q,y_q).

之后最大可能的幸福是什么 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.
  • 第二次握手时,高桥与Guest的左手握手 4 和客人的右手 5.
  • 第三次握手时,高桥与Guest的左手握手 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