分数: 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