← 返回题目
题库练习 [ABC149E] Handshake
← 上一题 下一题 →

A7537 | [ABC149E] Handshake

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

高桥作为特邀嘉宾参加了一个派对。派对上有 $N$ 位普通客人，第 $i$ 个普通客人有 $A_i$ 的权值。

高桥决定用 $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
5 3
10 14 19 34 33
输出 #1
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
C++ 编辑器
输入
输出