101494: [AtCoder]ABC149 E - Handshake

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $500$ points

Problem Statement

Takahashi has come to a party as a special guest. There are $N$ ordinary guests at the party. The $i$-th ordinary guest has a power of $A_i$.

Takahashi has decided to perform $M$ handshakes to increase the happiness of the party (let the current happiness be $0$). A handshake will be performed as follows:

  • Takahashi chooses one (ordinary) guest $x$ for his left hand and another guest $y$ for his right hand ($x$ and $y$ can be the same).
  • Then, he shakes the left hand of Guest $x$ and the right hand of Guest $y$ simultaneously to increase the happiness by $A_x+A_y$.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

  • Assume that, in the $k$-th handshake, Takahashi shakes the left hand of Guest $x_k$ and the right hand of Guest $y_k$. Then, there is no pair $p, q$ $(1 \leq p < q \leq M)$ such that $(x_p,y_p)=(x_q,y_q)$.

What is the maximum possible happiness after $M$ handshakes?

Constraints

  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq N^2$
  • $1 \leq A_i \leq 10^5$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible happiness after $M$ handshakes.

Sample Input 1

5 3
10 14 19 34 33

Sample Output 1

202

Let us say that Takahashi performs the following handshakes:

  • In the first handshake, Takahashi shakes the left hand of Guest $4$ and the right hand of Guest $4$.
  • In the second handshake, Takahashi shakes the left hand of Guest $4$ and the right hand of Guest $5$.
  • In the third handshake, Takahashi shakes the left hand of Guest $5$ and the right hand of Guest $4$.

Then, we will have the happiness of $(34+34)+(34+33)+(33+34)=202$.

We cannot achieve the happiness of $203$ or greater, so the answer is $202$.

Sample Input 2

9 14
1 3 5 110 24 21 34 5 3

Sample Output 2

1837

Sample Input 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

Sample Output 3

8128170

Input

题意翻译

##### 题目描述 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 ##### 输出格式 一行 , 最大的欢乐值 --- [翻译者的个人中心](https://www.luogu.com.cn/user/324250) [翻译者的博客](https://324250.blog.luogu.org)

Source/Category

加入题单

上一题 下一题 算法标签：