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-----
5 3
10 14 19 34 33

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
import sys
import bisect
input = sys.stdin.readline


def main():
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    
    l, r = -1, 10**6
    while r-l > 1:
        k = (r+l)//2
        count = 0
        for i in range(n):
            count += n-bisect.bisect_left(a, k-a[i])
        
        if count > m:
            l = k
        else:
            r = k
    ans = 0
    count = 0
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] += b[i]+a[i]
    for i in range(n):
        index = bisect.bisect_left(a, r-a[i])
        ans += b[n]-b[index]+a[i]*(n-index)
        count += n-index
    
    if count < m:
        ans += (m-count)*l
    
    print(ans)
    
    
    
    
def __starting_point():
    main()

__starting_point()

import sys
import numpy as np

# 価値 x 以上の握手を全て行うとする
# 握手回数が決まる。左手ごとに集計できる。

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
A = np.array(sys.stdin.readline().rstrip().split(), np.int64)

A.sort()  # A を昇順に並び替える

# x より価値が高くなる握手の総数
#  -> a に対して、相手は x - a が必要
#   -> A = [a0, a1, a2, ...] に対して、[x-a0の開始位置, x-a1の開始位置, x-a2の開始位置,...] を探す
def shake_cnt(x):
    # x 以上の握手を全て行うとして、握手の回数を数える行わない握手を数える
    X = np.searchsorted(A, x - A)  # ソートされたリストA に対して、x - A が挿入される位置を返す
    return N * N - X.sum()  # index の和は「小さい方」を指しているので、引く


# 二分探索  握手の回数が
left = 0  # 握手の回数がM以上
right = 10 ** 6  # 握手の回数がM未満 <- まだ足りない側
while 1 < right - left:  # left と right が隣り合ったら終了
    x = (left + right) // 2
    if shake_cnt(x) >= M:
        left = x
    else:
        right = x

# M回には届かないけれど、M回に限りなく近くなる価値 x = right
X = np.searchsorted(A, right - A)  # 各a in A が握手を行わない人数のArray
shake = N * N - X.sum()  # ここまでの握手回数

Acum = np.zeros(N + 1, np.int64)  # 人数 -> 累積和
# Acum = [a0, a0+a1, a0+a1+a2, ....] を計算して、ai さんが k番目以降と握手をすれば
Acum[1:] = np.cumsum(A)  # cumsum [1,2,3,4,5,6,...] -> [1,3,6,10,15,21,...]

# 右手の幸福度は ai * ((a0+a1+...a(n-1)) - (a(k-1)+...+a(n-1))) を得られる
# 左手の幸福度は 回数だけで決まる（何人と握手とするか）
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) * left  # 不足分。1回の価値は M とわかっている

print(happy)


n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
from bisect import bisect_left,bisect_right
def check(mid):
  mm=0
  for i in range(n):
    if -(a[i]+a[0])<mid:break
    mm+=bisect_right(a,-(mid+a[i]))
  return mm
ok=0
ng=10**10+7
while ng!=ok+1:
  mid=(ok+ng)//2
  if check(mid)>=m:ok=mid
  else:ng=mid
b=[0]
for i in a:b.append(b[-1]+i)
ans=0
for i in range(n):
  if -(a[i]+a[0])<ok:break
  ind=bisect_right(a,-(ok+a[i]))
  ans+=a[i]*ind
  ans+=b[ind]
print(-(ans+(check(ok)-m)*ok))

from bisect import bisect_left, bisect_right
from itertools import accumulate


def ge_m(x, m, n):
    total = 0
    for v in a:
        delta = x - v
        idx = bisect_left(a, delta)
        total += (n - idx)
    return total >= m


n, m = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
cum = [0] + list(accumulate(a))  # 累積和

# 1回の握手であがる幸福度のうち、最も低いものを求める
l = 0
r = a[-1] * 2 + 1
while r - l > 1:
    mid = (l + r) // 2
    if ge_m(mid, m, n):
        l = mid
    else:
        r = mid

# 最も低い幸福度よりも大きい値を足す
num = 0  # 握手の回数
ans = 0
for v in a:
    idx = bisect_right(a, l - v)
    num += n - idx
    ans += v * (n - idx) + (cum[-1] - cum[idx])
# 足りない握手の回数分、最も低い幸福度を足す
ans += (l * (m - num))
print(ans)

import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,M = list(map(int, input().split()))
    A = np.array(sorted([int(i) for i in input().split()]))

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        x = (left + right) // 2

        count = N**2 - np.searchsorted(A, x-A).sum()

        if count >= M:
            left = x
        else:
            right = x

    bound = np.searchsorted(A, left-A)
    count = N**2 - bound.sum()
    diff = count - M
    ans = ((N - bound) * A * 2).sum() - diff * left

    print(ans)


def __starting_point():
    main()

__starting_point()

import bisect
from itertools import accumulate


N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))

S = [0] + list(accumulate(A))


def calc(x):
    _total = 0
    _num = 0
    for i in range(N):
        j = bisect.bisect_left(A, x - A[i])
        _num += N - j
        _total += S[N] - S[j]
        _total += A[i] * (N - j)
    return _total, _num


left = 0
right = 200005

while right - left > 1:
    center = (left + right) // 2
    if calc(center)[1] >= M:
        left = center
    else:
        right = center

total, num = calc(left)
ans = total
ans -= (num - M) * left
print(ans)


import bisect
import copy

n, m = map(int,input().split())
a = list(map(int,input().split()))

a.sort()
asum = [0]
tmp = 0
for i in range(n):
    tmp += a[i] 
    asum.append(tmp)

lb = 1
ub = 2*10**5 + 1
while ub - lb > 1:
    cx = (ub+lb)//2
    cnt = 0
    total = 0
    for ca in a:
        cy = cx - ca
        ci = bisect.bisect_left(a, cy)
        cnt += n - ci
        total += asum[n] - asum[ci] + (n - ci) * ca
    if cnt >= m:
        lb = cx
        ans = copy.deepcopy(total) - (cnt - m) * cx
    else:
        ub = cx

print(ans)

from bisect import bisect_left

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)


import sys
from bisect import bisect_right, bisect_left
from itertools import accumulate

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def is_ok(x):
        cnt = 0
        for a in A:
            t = x - a
            idx = bisect_right(A, t)
            cnt += n - idx
        return cnt < m

    n, m = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()
    ng, ok = 0, 10 ** 15 + 1
    mth = meguru_bisect(ok, ng)
    R = [0] + list(accumulate(A))

    res = 0
    cnt = 0
    for a in A:
        s = mth - a
        left = bisect_left(A, s)
        res += (n - left) * a + R[-1] - R[left]
        cnt += n - left
    print((res - mth * (cnt - m)))


def __starting_point():
    resolve()

__starting_point()


8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from bisect import bisect_left
from itertools import accumulate
 
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A_r = list(reversed(A))
B = [0] + list(accumulate(A_r))
 
def func(x):
    count = 0
    for Ai in A:
        idx = bisect_left(A,x-Ai)
        count += N-idx
    if count >= M:
        return True
    else:
        return False
 
MIN = 0
MAX = 2*10**5+1
while MAX-MIN > 1:
    MID = (MIN+MAX)//2
    if func(MID):
        MIN = MID
    else:
        MAX = MID
 
ans = 0
count = 0
 
for Ai in A_r:
    idx = bisect_left(A,MIN-Ai)
    ans += Ai*(N-idx) + B[N-idx]
    count += N-idx
print(ans-(count-M)*MIN)

def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    count = 0
    acc = [0]
    for i in l:
        acc.append(acc[-1]+i)
    for i in l:
        index = bisect.bisect_left(l,right-i)
        ans += i*(n-index) + acc[n]-acc[index]
        count += n-index

    print(ans-(count-k)*left)
def __starting_point():
    main()
__starting_point()

def main():
    N, M = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())), reverse=True)
    def helper(x):
        p = len(A) - 1
        t = 0
        for a in A:
            while p >= 0 and A[p] + a < x:
                p -= 1
            t += p + 1
        return t
    l, r = 0, A[0] * 2 + 1
    while r - l > 1:
        m = (l + r) // 2
        if helper(m) > M:
            l = m
        else:
            r = m
    k = sum(A)
    p = len(A) - 1
    t = (M - helper(l)) * l
    for a in A:
        while p >= 0 and A[p] + a < l:
            k -= A[p]
            p -= 1
        t += a * (p + 1) + k
    print(t)

main()


import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict




def fft(A,B,fft_len=2*10**5):
    x = irfft(rfft(A,fft_len) * rfft(B,fft_len))+0.5
    return x.astype(int)


def main():
    N,M=mi()
    A=list(mi())

    counter = Counter()
    for a in A: 
        counter.add(a)
    
    count_map = counter.get_dict()
    F=[0]*2*10**5
    for a,count in count_map.items():
        F[a] = count
    
    G = fft(F,F,fft_len=1<<18)

    ans = 0
    handshake = M
    for x in range(len(G)-1,1,-1):
        if G[x] <= 0: continue
        count = G[x]
        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x

        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)



def __starting_point():
    main()
__starting_point()

#python3
from bisect import bisect_left
INF = int(1e9)

def main():
    n, m = list(map(int, input().split()))
    a = [int(i) for i in input().split()]
    a.sort()
    ac = [0]
    for i in range(n):
        ac.append(ac[i]+a[i])

    def chk(x):
        cnt = 0
        for i in range(n):
            pos = bisect_left(a, x - a[i])
            cnt += (n-pos)
        return (cnt < m)

    l = 0
    r = INF
    while r-l > 1: 
        mid = (l + r)//2
        if chk(mid):
            r = mid
        else:
            l = mid

    cnt = 0
    sgm = 0
    for i in range(n):
        pos = bisect_left(a, r - a[i])
        cnt += (n-pos) 
        sgm += a[i] * (n-pos) + (ac[n] - ac[pos]) 

    print((sgm+(m-cnt)*l))
main()


import numpy as np

n, m = map(int,input().split())
a = list(map(int,input().split()))

a.sort()
na = np.zeros(2**18)
for i in a:
    na[i] += 1

fa = np.fft.fft(na)

c = np.round(np.fft.ifft(fa*fa)).astype(int)

ans = 0
cm = 0
for i in range(2**18 - 1, 1, -1):
    cm += c[i]
    ans += i*c[i]
    if cm > m:
        ans -= i * (cm - m)
    if cm >= m:
        break

print(ans)

import sys
readline = sys.stdin.readline

N,M = list(map(int,readline().split()))
A = sorted(list(map(int,readline().split())))

sumA = [0] + A.copy()
for i in range(1,len(sumA)):
  sumA[i] += sumA[i - 1]
  
# 左手34,33,19,14,10
# 右手34,33,19,14,10
# X以上の握手をできる組だけ採用する
# 例：50以上の握手をできるのは、
# 左手34に対しては34,33,19
# 右手33に対しては34,33,19
# この合計がM回を越えると採用できない。
# M回を下回る場合は、すべての握手の合計で最大値を更新

ok = -1
ng = 10 ** 5 * 2 + 1

import bisect
def isOk(x):
  # x以上の握手だけ採用するとき、採用できる場合に全体の合計点はいくつになるか
  cnt = 0
  for left in A:
    right = x - left
    ind = bisect.bisect_left(A, right)
    cnt += N - ind
  if cnt > M:
    return True
  else:
    return False

while abs(ng - ok) > 1:
  mid = abs(ng + ok) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
    
# ok以上の握手だけ許容する場合の点数を算出
ans = 0
num = 0
for left in A:
  right = ok - left
  ind = bisect.bisect_left(A, right)
  ans += sumA[-1] - sumA[ind] + (N - ind) * left
  num += N - ind

if num > M:
  ans -= (num - M) * ok

print(ans)


N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**6

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(list(map(max,x)))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans






N,M = m()

a = l()

a.sort()

aaa = s(a)



po = [0 for i in range(10**5+1)]
ans = 0
for i in range(N):
    po[a[i]] += 1
for i in range(10**5-1,-1,-1):
    po[i] += po[i+1]
ll = 0
rr = 10**5 * 2

while True:
    mid = (ll+rr)//2
    if mid == ll:
        co = 0
        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                co += N
            else:
                co += po[mid-ui]
        cco = 0
        mid = rr

        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                cco += N
            else:
                cco += po[mid-ui]
        
        

        if co == cco:
            mid = rr

        elif cco == M:
            mid = rr
            co=cco

        else:
            mid = ll

        break

    co = 0
    for i in range(N):
        ui = a[i]
        if mid > ui + 10**5:
            continue
        elif ui >= mid:
            co += N
        else:
            co += po[mid-ui]
    
    if co < M:
        rr = mid                 
    else:
        ll = mid


a.sort(reverse = True)
dp = [0]

ans -= mid * (co - M)



for i in range(N):
    dp.append(dp[-1]+a[i])

for i in range(N):
    pl = a[i]
    if pl >= mid:
        ans += pl*N + dp[-1]
        
    elif pl + 10**5 < mid:
        continue
    else:
        ans += pl*po[mid-pl] + dp[po[mid-pl]]
print(ans)





from itertools import accumulate
from bisect import bisect_left

n, m = list(map(int, input().split()))
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
c = 0
s = 0


def f(x):
    nonlocal c, s
    c = 0
    s = 0
    for i in range(n):
        left = bisect_left(a, x - a[i])
        c += n - left
        s += cs[n] - cs[left] + (n - left) * a[i]
    return c


ok = 0
ng = 2 * 10 ** 5 + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    if f(x) >= m:
        ok = x
    else:
        ng = x

print((s - (c - m) * ok))


from bisect import bisect_left
n, m = map(int, input().split())
import math
import numpy as np
import decimal
import collections
import itertools
import sys
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = list(map(int, input().split()))
a.sort(reverse=True)
l, r = 0, 10 ** 6
while r - l > 1:
    m2 = (l + r) // 2
    cnt = 0
    ind = n - 1
    for i in a:
        while ind >= 0 and a[ind] + i < m2:
            ind -= 1
        cnt += ind + 1
    if cnt >= m:
        l = m2
    else:
        r = m2
cum = [0]
for i in a:
    cum.append(cum[-1] + i)
ans = 0
cnt2 = 0
ind2 = n - 1
b = l
for i in a:
    while ind2 >= 0 and a[ind2] + i < b:
        ind2 -= 1
    cnt2 += ind2 + 1
    ans += (ind2 + 1) * i + cum[ind2 + 1]
print(ans - (cnt2 - m) * b)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
l = 0
r = 3*10**5
while r - l > 1:
    m = (r + l)//2 # 和がm以上になるペアはいくつ？
    ind = N-1
    cnt = 0
    for a in A:
        while ind >= 0 and A[ind] + a < m:
            ind -= 1
        cnt += ind+1
    if cnt >= M:
        l = m
    else:
        r = m

B = [0]
for a in A:
    B.append(B[-1]+a)

ans = 0
border = l
ind = N-1
cnt = 0
for a in A:
    while ind >= 0 and A[ind] + a < border:
        ind -= 1
    cnt += (ind+1)
    ans += a*(ind+1) + B[ind+1]

ans -= (cnt-M)*border

print(ans)

def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*(10**5)+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    C=n-np.searchsorted(A,right-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    print(np.sum(A*C)+left*(m-cnt)+B[C[np.where(C>0)]-1].sum())
def __starting_point():
    main()
__starting_point()

import sys
from itertools import accumulate
from bisect import bisect_left

n, m, *a = list(map(int, sys.stdin.read().split()))
a.sort()


def f(x):
    # 幸福度がx未満となる組み合わせの個数を数える
    cnt = 0
    for ai in a:
        cnt += bisect_left(a, x-ai)
    # 幸福度がx以上の組み合わせの個数がm未満かどうか
    return n * n - cnt < m


left = a[0] * 2
right = a[-1] * 2
while right - left > 1:
    mid = (right + left) // 2
    if f(mid):
        right = mid
    else:
        left = mid
ans = 0
cumsum = [0] + list(accumulate(a))
j = 0
for ai in a:
    i = bisect_left(a, left-ai)
    j += n - i
    ans += ai * (n - i) + cumsum[-1] - cumsum[i]
ans += (m - j) * left
print(ans)


# 過去の提出を見ながら解いた

def main():
    N, M = list(map(int, input().split()))
    *a, = list(map(int, input().split()))
    a.sort()

    def count(mid) -> int:
        cnt = 0  # (i,j)>=mid の個数
        j = N  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
        for i in range(N):
            while j > 0 and a[i] + a[j - 1] >= mid:
                j -= 1
            # j==0 or a[i]+a[j]>=mid
            # j==0
            # 現在のiに対しすべてのaの要素が相方になる。
            # 一度そのようなiに達したら、それ以降のiはすべてこの条件を満たす。
            cnt += N - j  # iに対し[j,N)が相方になる
        return cnt

    def binary_search(*, ok: int, ng: int, is_ok: 'function') -> int:
        """あるペア和以上のみ採用する場合に
        M回以上握手できないようなペア和の上限"""
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    ma = binary_search(ok=2 * 10 ** 5 + 1, ng=0, is_ok=lambda mid: count(mid) < M)

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    *acc, = accumulate(a)

    ans = 0
    j = N  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
    for i in range(N):
        while j > 0 and a[i] + a[j - 1] >= ma:
            j -= 1
        ans += a[i] * (N - j) + acc[N] - acc[j]  # i側の寄与=ペア数,j側の寄与=acc
    ans += (ma - 1) * (M - count(ma))  # ペア和maではMペア組めないが、ma-1で埋められる

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
import numpy as np

# 価値 x 以上の握手を全て行うとする
# 握手回数が決まる。左手ごとに集計できる。

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
A = np.array(sys.stdin.readline().rstrip().split(), np.int64)

A.sort()  # A を昇順に並び替える

# x より価値が高くなる握手の総数
#  -> a に対して、相手は x - a が必要
#   -> A = [a0, a1, a2, ...] に対して、[x-a0の開始位置, x-a1の開始位置, x-a2の開始位置,...] を探す
def shake_cnt(x):
    # x 以上の握手を全て行うとして、握手の回数を数える行わない握手を数える
    X = np.searchsorted(A, x - A)  # ソートされたリストA に対して、x - A が挿入される位置を返す
    return N * N - X.sum()  # index の和は「小さい方」を指しているので、引く


# 二分探索  握手の回数が
left = 0  # 握手の回数がM以上
right = 10 ** 6  # 握手の回数がM未満 <- まだ足りない側
while 1 < right - left:  # left と right が隣り合ったら終了
    x = (left + right) // 2
    if shake_cnt(x) >= M:
        left = x
    else:
        right = x

# M回には届かないけれど、M回に限りなく近くなる価値 x = right
X = np.searchsorted(A, right - A)  # 各a in A が握手を行わない人数のArray
shake = N * N - X.sum()  # ここまでの握手回数

Acum = np.zeros(N + 1, np.int64)  # 人数 -> 累積和
# Acum = [a0, a0+a1, a0+a1+a2, ....] を計算して、ai さんが k番目以降と握手をすれば
Acum[1:] = np.cumsum(A)  # cumsum [1,2,3,4,5,6,...] -> [1,3,6,10,15,21,...]

# 右手の幸福度は ai * ((a0+a1+...a(n-1)) - (a(k-1)+...+a(n-1))) を得られる
# 左手の幸福度は 回数だけで決まる（何人と握手とするか）
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) * left  # 不足分。1回の価値は M とわかっている

print(happy)


import bisect


def is_ok(a, target, m):
    num = 0
    for val in a:
        index = bisect.bisect_left(a, target - val)
        num += len(a) - index
    if num <= m:
        return True
    else:
        return False


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))

a.sort()

ok, ng = 10 ** 10, -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(a, mid, m):
        ok = mid
    else:
        ng = mid

rui = [0] * (n + 1)

for i in range(n):
    rui[i+1] = rui[i] + a[i]

cnt = 0
ret = 0

for val in a:
    index = bisect.bisect_left(a, ok - val)
    num = len(a) - index
    cnt += num
    ret += (num * val) + (rui[-1] - rui[index])

ret += (m - cnt) * ng

print(ret)


from itertools import accumulate
from bisect import bisect_left, bisect_right
N, M = list(map(int, input().split()))
*A, = list(map(int, input().split()))
A.sort()
acc = list(accumulate(A[::-1]))[::-1]+[0]


def isok(x):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, x-a)
    return cnt >= M


l = 0
r = 202020
while l+1 < r:
    m = (l+r)//2
    if isok(m):
        l = m
    else:
        r = m

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, l-a)
    ans += a*(N-i) + acc[i]
    cnt += N-i
if cnt > M:
    ans -= l * (cnt-M)
print(ans)


import numpy as np
def convolve(A, B):
    # 畳み込み  # 要素は整数
    # 3 つ以上の場合は一度にやった方がいい
    dtype = np.int64
    fft, ifft = np.fft.rfft, np.fft.irfft
    a, b = len(A), len(B)
    if a == b == 1:
        return np.array([A[0]*B[0]])
    n = a+b-1  # 返り値のリストの長さ
    k = 1 << (n-1).bit_length()
    AB = np.zeros((2, k), dtype=dtype)
    AB[0, :a] = A
    AB[1, :b] = B
    return np.rint(ifft(fft(AB[0]) * fft(AB[1]))).astype(np.int64)[:n]

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = list(map(int, input().split()))
 
cnt = np.zeros(100001)
for i in a:
    cnt[i] += 1 

c = convolve(cnt,cnt)
ans = 0
for i in range(len(c))[::-1]:
    if c[i] > 0:
      p = min(m,c[i])
      m -= p
      ans += i*p
      if m == 0:
        break
print(ans)

# https://atcoder.jp/contests/abc149/tasks/abc149_e

# すべての握手の組み合わせN**2を列挙しソートしM番目までを足し合わせればOK
# だけど制約からこれを行うことは困難
# すべてを列挙しなくともM番目の値を知ることは二分探索で可能(参考:億マス計算)
# Aの累積和を保持しておけば、M番目の値の探索中にMまでの値の合計もついでに計算できる
# 以下reverseでソート済みだと仮定
# XがM番目の数→X以上である数はM個以上(cntとする)→cntがM個以上の条件を満たすうちの最大となるXがM番目の値
# そのあと余分な分を引く処理とか必要

from bisect import bisect_right, bisect_left
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N, M = read_ints()
A = read_ints()
A.sort()  # bisectを使う都合上 reverseは抜き
A_reversed = list(reversed(A))
A_rev_acc = cumsum1d(A_reversed)


def is_ok(X):
    # M番目の数はXである→X以上の個数>=M となるうちで最大のX(もっとも左の方のX)
    # X以上の個数>=Mを返す
    # X以下の個数はai+aj>=Xを満たす個数
    cnt = 0
    ans = 0
    for a in A:
        aa = X - a
        idx_reverse = N - bisect_left(A, aa)  # 大きい方からだと何番目か
        # これはbisect_right(A_reversed,aa)に等しい
        cnt += idx_reverse
        ans += A_rev_acc.total(0, idx_reverse) + idx_reverse * a
    return cnt >= M, ans, cnt


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        flg, ans, cnt = is_ok(mid)
        if flg:
            ok = mid
            ans_true = ans  # さいごにokとなる状態がans
            cnt_true = cnt
        else:
            ng = mid
    return ans_true, ok, cnt_true


ans_tmp, M_th_num, M_plus_alpha_th = \
    meguru_bisect(2 * 10 ** 5 + 1, 0)
# print(ans_tmp, M_th_num, M_plus_alpha_th)
print((ans_tmp - (M_plus_alpha_th - M) * M_th_num))


import bisect
n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
r=[0]*(10**5+2)
for i in range(n):
    r[l[i]]+=1
for i in range(10**5+1):
    r[i+1]+=r[i]
ok=10**6
ng=0
while ok-ng>1:
    x=(ok+ng)//2
    k=0
    for i in range(n):
        if x-l[i]<0:
            k+=n
        elif x-l[i]>10**5+1:
            k+=0
        else:
            k+=n-r[x-l[i]]
    if k>=m:
        ng=x
    else:
        ok=x
#print(ok)
p=[0]*(n+1)
for i in range(n):
    p[i+1]=p[i]+l[i]
ans=0
mi=0
for i in range(n):
    li=bisect.bisect_left(l,ok-l[i])
    ans+=l[i]*(n-li)+p[n]-p[li]
    mi+=n-li
print((ans-(mi-m)*ok))


import numpy as np
from numpy.fft import rfft, irfft

N, M = list(map(int, input().split()))
*A, = list(map(int, input().split()))
B = np.zeros(5*10**5)
for a in A:
    B[a] += 1

L = 5*10**5
FB = rfft(B, L)
C = np.rint(irfft(FB*FB)).astype(int)

ans = 0
for i in range(2*10**5, -1, -1):
    c = C[i]
    if not c:
        continue
    if M - c > 0:
        ans += i*c
        M -= c
    else:
        ans += i*M
        break
print(ans)


import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(list(map(max,x)))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans






N,M = m()

a = l()

a.sort()

aaa = s(a)



po = [0 for i in range(10**5+2)]
ans = 0
for i in range(N):
    po[a[i]] += 1
for i in range(10**5,-1,-1):
    po[i] += po[i+1]
ll = 0
rr = 10**5 * 2 + 1

while True:
    mid = (ll+rr)//2
    if mid == ll:
        co = 0
        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                co += N
            else:
                co += po[mid-ui]
        cco = 0
        mid = rr

        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                cco += N
            else:
                cco += po[mid-ui]

        if cco == M:
            mid = rr
            co=cco

        else:
            mid = ll

        break

    co = 0
    for i in range(N):
        ui = a[i]
        if mid > ui + 10**5:
            continue
        elif ui >= mid:
            co += N
        else:
            co += po[mid-ui]
    
    if co < M:
        rr = mid                 
    else:
        ll = mid


a.sort(reverse = True)
dp = [0]

ans -= mid * (co - M)



for i in range(N):
    dp.append(dp[-1]+a[i])

for i in range(N):
    pl = a[i]
    if pl >= mid:
        ans += pl*N + dp[-1]
        
    elif pl + 10**5 < mid:
        continue
    else:
        ans += pl*po[mid-pl] + dp[po[mid-pl]]
print(ans)





#!/usr/bin/env python3

import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, sums):
    ss = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ss += sums[n] - sums[idx]
        ss += (n - idx) * a
    #print(mins)
    return ss

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = max(A) * 2 + 1
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    cnt = _count(A, N, l)
    ret = _sum(A, N, l, sums)
    ret -= (cnt - M) * l
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print((i, j))
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print((j, i))
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

def __starting_point():
    main()

__starting_point()

import bisect
import itertools
import numpy as np

def search_cut(N, M, A):
    high_cut = A[-1] * 2
    low_cut = A[0] * 2

    while high_cut > low_cut + 1:
        mid = (high_cut + low_cut) // 2
        count = (N  - np.searchsorted(A, mid - A, side = 'left')).sum()

        if count > M:
            low_cut = mid
        else:
            high_cut = mid

    return low_cut, high_cut

def happiness(N, M, A, low_cut, high_cut):
    A_sum = np.zeros(N + 1)
    A_sum[1:] = np.cumsum(A)
    X = np.searchsorted(A, high_cut - A, side = 'left')
    happiness = (A_sum[-1] - A_sum[X]).sum()
    happiness += ((N - X) * A).sum()
    happiness += (M - (N - X).sum()) * low_cut

    return int(happiness)


N, M = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
A = np.sort(A)

low_cut, high_cut = search_cut(N, M, A)
ans = happiness(N, M, A, low_cut, high_cut)
print(ans)


ii = lambda : int(input())
mi = lambda : list(map(int,input().split()))
li = lambda : list(map(int,input().split()))

n,m = mi()
alis = li()

alis.sort()
ok = 0
ng = alis[n-1] * 2 +1
from bisect import bisect_left as bl
while ng - ok >1:
    mid = (ok + ng)//2
    ima = 0
    for i in range(n):
        ima += n - bl(alis,mid-alis[i])
    if ima >= m:
        ok = mid
        outrange = ima - m
    else:
        ng = mid

acu_alis = [0]*n
ima = 0
for i in range(n):
    acu_alis[i] = alis[i] + ima
    ima = alis[i] + ima

ans = 0
for i in range(n):
    tmp = bl(alis,ok-alis[i]) 
    if tmp ==0:
        ans += n*alis[i] + acu_alis[n-1]
    else:
        ans += (n-tmp)*alis[i] + acu_alis[n-1] - acu_alis[tmp-1]
ans -= outrange*ok
print(ans)




n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
acum=[arr[0]]
for i in range(1,n):
  acum.append(acum[-1]+arr[i])
l=0
r=2*10**5+1
while r-l!=1:
  mid=(l+r)//2
  tmp=0
  cnt=0
  pos=n-1
  for i in range(n):
    while pos!=-1:
      if arr[i]+arr[pos]>=mid:
        cnt+=pos+1
        tmp+=arr[i]*(pos+1)+acum[pos]
        break
      else:
        pos-=1
        if pos==-1:
          break
  if cnt<=m:
    r=mid
  else:
    l=mid
tmp+=(m-cnt)*l
print(tmp)

from bisect import bisect_left

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)


def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))
    an = aa[n]

    ok = 0
    ng = 10**10
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if sum([n-bl(a, mid-a[i]) for i in range(n)]) >= m:
            ok = mid
        else:
            ng = mid

    c = -m+sum([n-bl(a, ok-a[i]) for i in range(n)])
    ans = -c*ok
    for i in range(n):
        d = bl(a, ok-a[i])
        ans += an-aa[d]+(n-d)*a[i]
    print(ans)


main()

def e_handshake():
    import numpy as np
    N, M = [int(i) for i in input().split()]
    A = np.array(input().split(), np.int64)
    A.sort()

    def shake_cnt(x):
        # 幸福度が x 以上となるような握手を全て行うときの握手の回数
        # 全体から行わない握手回数を引く
        return N**2 - np.searchsorted(A, x - A).sum()

    # 幸福度の上昇が right 以上となるような握手はすべて行い、
    # left となるような握手はいくつか行って握手回数が M 回になるようにする
    left = 0
    right = 10 ** 6
    while right - left > 1:
        mid = (left + right) // 2
        if shake_cnt(mid) >= M:
            left = mid
        else:
            right = mid

    # 幸福度が right 以上上がるような握手をすべて行ったとして、回数と総和を計算
    X = np.searchsorted(A, right - A)  # 行わない人数
    Acum = np.zeros(N + 1, np.int64)  # 累積和で管理する
    Acum[1:] = np.cumsum(A)
    happiness = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

    # 幸福度が right 未満の上昇となる握手を、握手回数が M になるまで追加で行う
    shake = N * N - X.sum()
    happiness += (M - shake) * left
    return happiness

print(e_handshake())

import numpy as np
from numpy.fft import rfft,irfft
N,M = map(int,input().split())
A = list(map(int,input().split()))
a = np.zeros(10**5+1)
for i in range(N):
    a[A[i]] += 1
b = rfft(a,2*10**5+1)
b = irfft(b*b,2*10**5+1)
b = np.rint(b).astype(np.int64)
c = 0
ans = 0
for n in range(2*10**5,1,-1):
    if c+b[n]<M:
        c += b[n]
        ans += b[n]*n
    else:
        ans += (M-c)*n
        c = M
        break
print(ans)


import numpy as np
N, M = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = np.fft.rfft(x, fft_size)
conv = np.fft.irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
    h = happy.pop()
    num = cnt.pop()
    num = min(M, num)

    M -= num
    ans += num * h

print(ans)



from bisect import bisect_left
from itertools import accumulate

def resolve():
    def getCount(x):
        cnt = 0
        for a in A:
            # X未満の個数
            idx = bisect_left(A, x - a)
            # X以上の個数
            cnt += N - idx
        # X以上を使う！と決めた時、M個以上になるか
        return cnt >= M

    N, M = list(map(int, input().split()))
    A = sorted(map(int, input().split()))

    ng = 10 ** 9
    ok = 0
    # X以上を使う！と決めるとX以上の個数が自明にわかる。
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if getCount(mid):
            ok = mid
        else:
            ng = mid

    # M個以上あることがわかれば、Mよりも余分な数(同じ値が複数ある場合)
    # はすべてXである事がわかるため、差分だけ引けば良い。
    B = [0] + list(accumulate(A))
    ans = 0
    cnt = 0
    for i in range(N):
        idx = bisect_left(A, ok - A[i])
        ans += B[N] - B[idx] + A[i] * (N - idx)
        cnt += N - idx

    rest = (cnt - M) * ok
    print((ans - rest))


def __starting_point():
    resolve()

__starting_point()

from bisect import bisect_left

N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
l = 0
r = 2*10**5+5


while l+1 < r:
    mid = (l+r) // 2
    
    m = 0
    for a in A:
        idx = bisect_left(A, mid-a)
        m += N-idx
        
    if m >= M: l = mid
    else: r = mid

s = [0] * (N+1)
for i in range(N):
    s[i+1] = s[i] + A[i]
    
ans = 0
m = 0
for a in A:
    idx = bisect_left(A, l-a)
    m += N-idx
    
    ans += s[N]-s[idx]
    ans += a*(N-idx)
    
ans -= (m-M)*l

print(ans)

import sys
input = sys.stdin.readline

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)


from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, M = list(map(int, input().split()))
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for k, A in enumerate(As, start=1):
            i = bisect_left(As, x-A)
            num += N-i
            if num >= M:
                return True
            elif num + (N-k)*N < M:
                return False
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    score = 0
    num = 0
    accAs = list(accumulate([0]+As))
    for A in As:
        i = bisect_right(As, ok-A)
        score += A*(N-i) + accAs[N] - accAs[i]
        num += N-i
#    print('score:', score, '/ num:', num)

    ans = score + ok*(M-num)
    print(ans)


solve()


def binary_search(*, ok, ng, is_ok):
    while abs(ok - ng) > 1:
        mid = (ng + ok) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    from itertools import accumulate

    N, M = list(map(int, input().split()))
    *A, = sorted(map(int, input().split()))

    acc = [0]
    for x in accumulate(A):
        acc.append(x)

    def count(h):
        ret = 0

        j = N
        for i in range(N):
            while j - 1 >= 0 and A[i] + A[j - 1] >= h:
                j -= 1
            ret += N - j
            # [j,N)の要素数

        return ret

    x = binary_search(ok=A[-1] * 2 + 1, ng=0, is_ok=lambda x: count(x) < M)
    # 幸福度の総和がX以上のペア数がM未満となる最大のX

    s = 0
    j = N
    for i in range(N):
        while j - 1 >= 0 and A[i] + A[j - 1] >= x:
            j -= 1
        s += A[i] * (N - j) + acc[N] - acc[j]
    s += (M - count(x)) * (x - 1)

    print(s)


def __starting_point():
    main()

__starting_point()

from bisect import bisect_left
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
maxA = max(A)
cnt = [0] * (maxA * 2 + 2)
rui = [n] * (maxA * 2 + 2)

for a in A:
  cnt[a] += 1

accum = 0  
for i in range(maxA * 2 + 1):
  accum += cnt[i]
  rui[i + 1] -= accum 
  
# 左手を決めた時(left)に、幸福度がx 以上となる組み合わせの数を返す
def f(x):
  ret = 0
  for left in A:
    ret += rui[max(x - left, 0)]
  return ret
  
lo = 0
hi = maxA * 2 + 1
while hi - lo > 1:
  md = (lo + hi) // 2
  if f(md) >= m:
    lo = md
  else:
    hi = md 
# もとまる lo が m 通り以上握手ができる最小の数。
    
ruiA = [0] * (n + 1)
for i in range(n):
  ruiA[i + 1] = ruiA[i] + A[i]

ans = 0
cnt = 0
for i in range(n):
  pos = bisect_left(A, lo - A[i])
  cnt += n - pos
  ans += ruiA[-1] - ruiA[pos] + A[i] * (n - pos)
if cnt == m:
  print(ans)
else: # m個よりも多い分を引く
  rem = cnt - m
  print(ans - rem * lo)

import numpy as np
n, k = list(map(int, input().split()))
a = np.array(list(map(int, input().split())))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = n * n - a.searchsorted(m - a).sum()
    if res >= k:
        l = m
    else:
        r = m
b = np.array([0] * (n + 1))
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - a.searchsorted(l - x)
    ans += b[t] + x * t
    cnt += t
print((ans - (cnt - k) * l))


import sys
input = sys.stdin.readline

mm = 10**10
k = mm.bit_length()
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(200001)]]

n,m = map(int, input().split())
a = [int(i) for i in input().split()]
b = [0]*100001

for i in a:
    b[i] += 1
    
c = li(st(nu(b)*nu(b)))
ans = 0
for i in range(200001)[::-1]:
    if c[i] > 0:
      p = min(m,c[i])
      m -= p
      ans += i*p
      if m == 0:
        break
print(ans)

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" どのパワー以上の組み合わせまで握手するのか二分探索で調べる
    同じパワーとなる組み合わせに注意 """
N, M = lr()
A = np.array(lr())
A.sort()

def check(x):
    # x以上の幸福度で握手した時、M回以下だとTrueを返す
    Y = np.searchsorted(A, x - A)
    return N*N - Y.sum() <= M

ok = 10 ** 6; ng = 0
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, ok-A)
answer = (Acum[-1] - Acum[Y]).sum() + (A * (N-Y)).sum()
answer += ng * (M - (N-Y).sum())
print(answer)
# 24


def judge(k, N, A):
    p = N - 1
    t = 0
    for i in A:
        while p >= 0 and A[p] + i < k:
            p -= 1
        t += (p + 1)
    return t
def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    r = 0
    p = N - 1
    k = sum(A)
    for i in A:
        while p >= 0 and A[p] + i < X :
            k -= A[p]
            p -= 1
        r += i * (p + 1) + k
    return r - (judge(X, N, A) - M) * X
print((main()))


from bisect import bisect_left

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = A[-1] * 2 + 100
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)


from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open(0).read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**9
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

import numpy as np

n, m = list(map(int, input().split()))
A = np.array(input().split(), np.int64)
A = np.sort(A)

def is_ok(x):
    cnt = n**2-np.searchsorted(A, x-A, side='left').sum()
    if cnt >= m:
        return True
    else:
        return False

l = 0
r = 2*10**5+1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        l = c
    else:
        r = c

from itertools import accumulate
B = [0]+list(A)
B = list(accumulate(B))
ans = 0
cnt = 0
for a in A:
    j = np.searchsorted(A, l-a, side='left').sum()
    cnt += n-j
    ans += B[-1]-B[j]+a*(n-j)
ans -= (cnt-m)*l
print(ans)


import sys
input = sys.stdin.readline
from bisect import bisect_left
from itertools import accumulate

def func(A, N, M, x):
    count = 0
    for Ai in A:
        idx = bisect_left(A, x - Ai)
        count += N - idx
    if count >= M:
        return True
    else:
        return False

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    A_rev = list(reversed(A))
    B = [0] + list(accumulate(A_rev))
 
    min_ = 0
    max_ = 2 * 10 ** 5 + 1
    while max_ - min_ > 1:
        mid = (min_ + max_) // 2
        if func(A, N, M, mid):
            min_ = mid
        else:
            max_ = mid
    
    ans = 0
    count = 0
    for Ai in A_rev:
        idx = bisect_left(A, min_-Ai)
        ans += Ai * (N - idx) + B[N-idx]
        count += N - idx
    print(ans-(count-M)*min_)

def __starting_point():
    main()
__starting_point()

import numpy as np
N,M,*A = list(map(int, open(0).read().split()))
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)


def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l = np.array(l)
    def bise(x):
        y = np.searchsorted(l,x-l)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    
    acc = np.zeros(n+1,np.int64)
    acc[1:] = l.cumsum()
    x = np.searchsorted(l,right-l)
    count = n*n-x.sum()
    ans = (acc[-1]-acc[x]).sum() + (l*(n-x)).sum()

    print(ans-(count-k)*left)
def __starting_point():
    main()
__starting_point()

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
A = sorted(list(map(int,readline().split())))

ok = -1
ng = (10 ** 5) * 2 + 1

# x以上の握手ペアをM回以上作れるか、でxの最大値を二分探索
import bisect
def isOk(x):
  cnt = 0
  for left in A:
    right = x - left
    ind = bisect.bisect_left(A, right)
    cnt += N - ind
  return cnt >= M
  
while abs(ng - ok) > 1:
  mid = abs(ng + ok) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid

# okが基準とすべきxの値である

sumA = [0] + A.copy()
for i in range(1, len(sumA)):
  sumA[i] += sumA[i - 1]

ans = 0
num = 0
for left in A:
  right = ok - left
  ind = bisect.bisect_left(A, right)
  num += N - ind
  ans += (N - ind) * left + sumA[-1] - sumA[ind]
  
if num > M:
  ans -= (num - M) * ok
  
print(ans)  


from bisect import bisect_left, bisect_right
from itertools import accumulate
def resolve():
    def shake_cnt(x):
        cnt = 0
        pos = 0
        for i in range(N):
            pos = bisect_left(A, x - A[i])
            cnt += N - pos
        return cnt < M # X以上の和がM個未満かどうか

    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()

    # 終了時にngにX-1,okにXが入っている。
    ng = 0
    ok = 10 ** 6
    while abs(ok - ng) > 1:
        mid = (ok + ng)//2
        if shake_cnt(mid):
            ok = mid
        else:
            ng = mid

    acc = [0] + list(accumulate(A))
    ans = 0
    for i in range(N):
        pos = bisect_right(A, ng - A[i])
        cnt = N - pos
        ans += cnt * A[i] + (acc[N] - acc[pos])
        M -= cnt
    ans += M * ng
    print(ans)


def __starting_point():
    resolve()

__starting_point()

import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


def convolve(f, g):
    """多項式 f, g の積を計算する。

    Parameters
    ----------
    f : np.ndarray (int64)
        f[i] に、x^i の係数が入っている

    g : np.ndarray (int64)
        g[i] に、x^i の係数が入っている


    Returns
    -------
    h : np.ndarray
        f,g の積
    """
    # h の長さ以上の n=2^k を計算
    fft_len = 1
    while 2 * fft_len < len(f) + len(g) - 1:
        fft_len *= 2
    fft_len *= 2

    # フーリエ変換
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)

    # 各点積
    Fh = Ff * Fg

    # フーリエ逆変換
    h = np.fft.irfft(Fh, fft_len)

    # 小数になっているので、整数にまるめる
    h = np.rint(h).astype(np.int64)

    return h


N, M = inl()
A = inl()

power = np.zeros(10 ** 5 + 1, dtype=np.int64)
for i in range(N):
    power[A[i]] += 1

P = convolve(power, power)

r = M
ans = 0
for k in range(len(P) - 1, -1, -1):
    c = min(P[k], r)
    ans += k * c
    r -= c
    if r <= 0:
        break

print(ans)


import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print(("-------\n{}\n-------".format(text)))

INF=10**20
class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        
    
    def add(self,polynomial): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            

    def get_coefficient(self,dim):
        return self.f[dim]

    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)

    def convolve(self,g):
        h = self.fft(self.f,g)[:len(self.f) + len(g) - 1]
        self.f = h
    


def main():
    N,M=mi()
    A=list(mi())
    
    mx = 2*10**5+10
    F = PolySolver(mx,init_val=0)
    for a in A:
        F.add(Polynomial(dim=a).values)
    
    g = F.f
    F.convolve(g)

    ans = 0
    handshake = M
    for x in range(mx-1,1,-1):
        count = F.get_coefficient(x)
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

def __starting_point():
    main()

__starting_point()

import sys
import  math
import fractions
from collections import defaultdict
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: list(map(int, stdin.readline().split()))
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
A.sort()
S=[0]
S[0]=A[0]

for i in range(1,N):
    S.append(S[i-1]+A[i])

def clc_shake(x):#x以上の和
    tot=0
    for i in range(N):
        th=x-A[i]
        inds=bisect.bisect_left(A,th)
        tot+=(N-inds)
    return tot

l=0
r=2*(10**6)
c=0

while (l+1<r):
    c=(l+r)//2
    if(clc_shake(c)<M):
        r=c
    else:
        l=c


ans=0
for i in range(N):
        th=r-A[i]
        inds=bisect.bisect_left(A,th)
        if(inds!=0):
            ans+=((N-inds)*A[i]+(S[N-1]-S[inds-1]))
        else:
            ans+=((N-inds)*A[i]+(S[N-1]))


M2=M-clc_shake(r)
ans+=M2*(l)
print(ans)





import bisect
n,m = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]

def cnt(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += bisect.bisect_left(A,x - a)
    return res

def ans(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += a*bisect.bisect_left(A,x-a) + S[bisect.bisect_left(A,x-a)]
    return res

top = A[-1]*2+1
bottom = 0
# mid以上が何個あるか
while top - bottom > 1:
    mid = (top + bottom)//2
    if n*n - cnt(mid,A,S) > m:
        bottom = mid
    else:
        top = mid

print((S[-1]*2*n - ans(top,A,S) + bottom*(m - (n*n - cnt(top,A,S)))))


from bisect import bisect_left
def check(x):
  cnt=0
  l=n
  r=n
  for i in range(n):
    while True:
      if l==0:
        break
      if a[l-1]<x-a[i]:
        break
      l-=1
    cnt+=(r-l)
  return cnt>=m

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
ok=0
ng=2*10**5+10
# 幸福度が上位m個に入る最小のAx+Ayを二分探索する。
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if check(mid):
    ok=mid
  else:
    ng=mid

ru=[0]*(n+1)
for i in range(n):
  ru[i+1]=ru[i]+a[i]

ans=0
cnt=0
r=n
# 幸福度が上位m個に入るAx+Ayの最小値のみm個の個数制限から溢れてしまう場合があるので別に考える
ok=ok+1 # Ax+Ayの最小値より大きな値を先に処理するために最小値+1をする。
for i in range(n):
  # 最小値以外の処理
  l=bisect_left(a,ok-a[i])
  cnt+=r-l
  ans+=(r-l)*a[i]+(ru[r]-ru[l])
ans+=(ok-1)*(m-cnt) # 最小値の処理
print(ans)


from bisect import bisect_left

N,M=list(map(int,input().split()))
A=list(map(int,input().split()))

A.sort()

l=1
r=200000+1

def chk(x):
    c=0
    for la in A:
        y=bisect_left(A,x-la)
        c+=N-y
    if c>=M:
        return True
    else:
        return False



while l+1<r:
    mid=(l+r)//2
    if chk(mid):
        l=mid
    else:
        r=mid

AN=l

S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] > AN - la:
            rr = mi
        else:
            ll = mi
    c+=N-rr
    ans1=ans1+la*(N-rr)+S[N]-S[rr]

ans=ans1+(M-c)*AN
print(ans)




def main():
    import numpy as np
    n,m=list(map(int,input().split()))
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*10**5+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    s=np.sum(A*C)+border*(m-cnt)+B[C[np.where(C>0)]-1].sum()
    print(s)
def __starting_point():
    main()

__starting_point()

def main():
    import numpy as np
    n,m=list(map(int,input().split()))
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=10**10*1
    left=-10**10-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    #print(border,A,B,C)

    s,cnt=0,0
    for i in range(n):
        if C[i]>0:
          cnt+=C[i]
          s+=B[C[i]-1]+A[i]*C[i]
    s+=border*(m-cnt)

    print(s)
def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
import numpy as np

N,M = list(map(int,input().split()))
A = np.array(input().split(),np.int64)

A = np.sort(A)
S = np.zeros(N+1,np.int64)
S[1:]= np.cumsum(A)

hi = 200001
lo = -1

while hi-lo > 1:
    mid = (hi+lo)//2
    above_mid = (N-np.searchsorted(A,mid-A,side='left')).sum()
    if above_mid >= M:
        lo = mid
    else:
        hi = mid

X = np.searchsorted(A,hi-A,side='left')

above_hi = (N-X).sum()
happiness = (S[-1]-S[X]).sum()
happiness += (A*(N-X)).sum()
happiness += (M-above_hi)*lo

print(happiness)


import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print(("-------\n{}\n-------".format(text)))

INF=10**20
class Polynomial:
    def __init__(self,coefficient=None,dim=0,const=1):
        if coefficient == None:
            self.coefficient = np.zeros(dim+1, np.int64)
            self.coefficient[dim] = const
        else:
            self.coefficient = coefficient

    def __add__(self,other): # +
        f,g = self.coefficient, other.coefficient
        if len(f) > len(g): f,g = g,f

        h = Polynomial(dim=len(g)-1,const=0)
        h.coefficient[len(f):] += g[len(f):]
        h.coefficient[:len(f)] += f + g[:len(f)]
        return h
    
    def __iadd__(self,other): # +=
        h = self.__add__(other)
        self.coefficient = h.coefficient
        return self

    def __mul__(self,other): # *
        f = self.coefficient
        g = other.coefficient
        h = Polynomial()
        h.coefficient = self.fft(f,g)[:len(f)+len(g)-1]
        return h
    
    def __len__(self):
        return len(self.coefficient)

    def __getitem__(self,key):
        return self.coefficient[key]

    def get_coefficient(self,x):
        return self.coefficient[x]


    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)



def main():
    N,M=mi()
    A=list(mi())
    
    coefficient = [0] * (2*10**5+10)
    for a in A:
        coefficient[a] += 1
    
    f = Polynomial(coefficient=coefficient)
            
    g = f * f
    ans = 0
    handshake = M
    for x in range(len(g)-1,1,-1):
        count = g[x]
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

def __starting_point():
    main()

__starting_point()

from bisect import bisect_left

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    L, R = 0, 2 * 10**5 + 1
    while L+1 < R:
        P = (L+R)//2
        cnt = 0
        for v in a:
            x = P - v
            cnt += n - bisect_left(a, x)
        if cnt >= m:
            L = P
        else:
            R = P
    csum = [0]
    for v in a:
        csum.append(v)
    for i in range(n):
        csum[i+1] += csum[i]
    ans = 0
    cnt = 0
    for v in a:
        x = L - v
        idx = bisect_left(a, x)
        cnt += n-idx
        ans += csum[-1] - csum[idx]
        ans += v * (n - idx)
    ans -= (cnt - m) * L
    print(ans)

def __starting_point():
    main()
__starting_point()

from bisect import bisect_right as br
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
b=[0]
for i in a:b.append(b[-1]+i)
ng=2*10**5+7
ok=-1
while ok+1!=ng:
  mid=(ng+ok)//2
  co=0
  for i in a:co+=br(a,-(mid+i))
  if co<m:ng=mid
  else:ok=mid
ans=0
co=0
for i in a:
  ind=br(a,-(ok+i)-1)
  co+=ind
  ans+=-b[ind]-i*ind
ans+=(m-co)*ok
print(ans)

import numpy as np
from numpy.fft import rfft,irfft

def main():
    n,m=map(int,input().split())
    A=np.array(list(map(int,input().split())))
    F=np.bincount(A)
    fft_len=2*10**5+1
    Ff=rfft(F,fft_len)
    G=np.rint(irfft(Ff*Ff,fft_len)).astype(np.int64)
    G_acc=G.cumsum()
    remove_cnt=n**2-m
    border=np.searchsorted(G_acc,n**2-m)
    x=n**2-m-G_acc[border-1]
    remove_sum=(G[:border]*np.arange(border)).sum()+border*x
    ans=A.sum()*2*n-remove_sum
    print(ans)
    
def __starting_point():
    main()
__starting_point()

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(list(range(N))):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(list(range(N))):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print((main()))


n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

# l[i] = (a[j] >= i を満たすjの個数)
l = [n for i in range(a[0]+1)]
for i in range(2, n+1):
    for j in range(a[-i], a[-i+1], -1):
        l[j] = n - i + 1

# 二分探索
# a[i] + a[j] >= x を満たす(i, j)がm組以上存在する最小のxを求める
start = 2 * a[-1]
stop = 2 * a[0]
while start < stop:
    i = (start + stop + 1) // 2
    num = 0
    for j in a:
        if i - j < 0:
            num += n
        elif i - j <= a[0]:
            num += l[i - j]
        else:
            break

    if num >= m:
        start = i
    else:
        stop = i - 1

num = 0
for i in a:
    if start - i < 0:
        num += n
    elif 0 <= start - i <= a[0]:
        num += l[start - i]
    else:
        break

# start <= a[i]+a[j] を満たす a[i]+a[j] を全て足す
ans = 0
for i in a:
    if start - i < 0:
        ans += 2 * i * n
    elif start - i <= a[0]:
        ans += 2 * i * l[start - i]
    else:
        break
ans -= (num - m) * start
print(ans)

from bisect import bisect_left,bisect_right
from itertools import accumulate

n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()

def isOK(x):
    num=0
    for k,a in enumerate(A,start=1):
        i=bisect_left(A,x-a)
        num+=n-i
    return num>=m



l=0
r=2*10**5+1
while l+1<r:
    mid=(l+r)//2
    if isOK(mid):
        l=mid
    else:
        r=mid

s=0
num=0

acc=list(accumulate([0]+A))

for a in A:
    i=bisect_right(A,l-a)
    s+=a*(n-i)+acc[n]-acc[i]
    num+=n-i

ans=s+l*(m-num)

print(ans)


from bisect import bisect_left
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] = a[i] + b[i]
    ok = 0; ng = 2 * 10**5 + 5
    while ok+1 < ng:
        mid = (ok + 1 + ng) // 2
        buf = 0
        for i in range(n):
            p = mid - a[i]
            buf += n - bisect_left(a, p)
        if buf >= m:
            ok = mid
        else:
            ng = mid
    ans = 0
    num = 0
    tot = 0
    for i in range(n):
        p = ok - a[i]
        index = bisect_left(a, p)
        num += n - index
        tot += b[n] - b[index]
        tot += a[i] * (n-index)
    ans = tot - (num - m) * ok
    print(ans)

def __starting_point():
    main()
__starting_point()

import bisect
from itertools import accumulate
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A2 = [0]+list(accumulate(A))
def judge(mid):
    count = 0
    for i in range(N):
        border = mid - A[i]
        ind = bisect.bisect_left(A,border)
        count += N-ind
    if count < M:
        return True
    else:
        return False
mina = 0
maxa = 2*(10**5) + 1
while maxa-mina > 1:
    mid = (maxa+mina)//2
    if judge(mid):
        maxa = mid
    else:
        mina = mid
count = 0
ans = 0
for i in range(N):
    border = maxa - A[i]
    ind = bisect.bisect_left(A,border)
    count += N-ind
    ans += A[i]*(N-ind) + A2[N]-A2[ind]
if count == M:
    print(ans)
else:
    rem = M-count
    print(ans+rem*mina)

######################
# AC: ms(PyPy)
# AC: ms(Python3)
######################

from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = list(map(int, input().split()))
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print((ans * 2 - diff * left))


def __starting_point():
    main()

__starting_point()

from bisect import bisect_left
from itertools import accumulate
N,M,*A = list(map(int, open(0).read().split()))
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)



from bisect import bisect_left
from itertools import accumulate
def resolve():
    def getCount(x):
        count = 0
        for Ai in A:
            idx = bisect_left(A, x - Ai)
            count += N - idx
        return count >= M


    N, M = list(map(int, input().split()))
    A = sorted(map(int, input().split()))
    A_r = A[::-1]
    B = [0] + list(accumulate(A_r))

    MIN = 0
    MAX = 2 * 10 ** 5 + 1
    while MAX - MIN > 1:
        MID = (MIN + MAX) // 2
        if getCount(MID):
            MIN = MID
        else:
            MAX = MID

    ans = 0
    count = 0

    for Ai in A_r:
        idx = bisect_left(A, MIN - Ai)
        ans += Ai * (N - idx) + B[N - idx]
        count += N - idx
    print((ans - (count - M) * MIN))


def __starting_point():
    resolve()

__starting_point()

from itertools import accumulate

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
MAX = 10 ** 5

scores = [0] * (2 * MAX + 1)
for e in a:
    scores[e] += 1

acc = list(accumulate(scores))


def f(x):
    cnt = 0
    for e in a:
        cnt += n - acc[max(0, x - e - 1)]

    return cnt


l = 0
r = 2 * MAX + 1
while r - l > 1:
    mid = (l + r) // 2
    if f(mid) >= m:
        l = mid
    else:
        r = mid

scores_sum = [i * e for i, e in enumerate(scores)]
acc_sum = list(accumulate(scores_sum))
sm = sum(a)
ans = 0
cnt_sum = 0
for e in a:
    i = max(0, l - e - 1)
    cnt = n - acc[i]
    ans += e * cnt + sm - acc_sum[i]
    cnt_sum += cnt

ans -= (cnt_sum - m) * l

print(ans)


N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
A = list(map(int,readline().split()))

MAX_VAL = 10 ** 5 + 1
hand = [0] * MAX_VAL
for a in A:
  hand[a] += 1
  
import numpy as np
def convolve(f, g):
    fft_len = 1
    while 2 * fft_len < len(f) + len(g) - 1:
        fft_len *= 2
    fft_len *= 2
    
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)

    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:len(f) + len(g) - 1]

right_hand = np.array(hand, dtype = int)
left_hand = np.array(hand, dtype = int)

H = convolve(left_hand, right_hand)
# Hを大きいほうから見ていくと、
# 幸福度iの握手をH[i]種類できることが分かる
# 上から順に足していって、最後H[i]種類の握手を足せないときは、残りの握手回数だけ足す

ans = 0
for i in range(len(H) - 1, -1, -1):
  if H[i] == 0:
    continue
  if H[i] <= M: # H[i]回の握手ができる
    ans += i * H[i]
    M -= H[i]
  else: # H[i]回の握手ができないので、残った回数だけ握手する
    ans += M * i
    break

print(ans)

from bisect import bisect_left


def solve(m):
    r = N - 1
    l = 0
    cnt = 0
    while 0 <= r and l < N:
        if A[r] + A[l] < m:
            l += 1
        else:
            cnt += N - l
            r -= 1
    return cnt


N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + A[i]

# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = 0
ng = 10 ** 21
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = solve(mid)
    if cnt >= M:
        ok = mid
    else:
        ng = mid

X = ok
amari = float('inf')
cnt = 0
score = 0
for i, Ai in enumerate(A):
    Aj = X - Ai
    j = bisect_left(A, Aj)
    score += S[N] - S[j] + Ai * (N - j)
    cnt += N - j
    if j < N:
        amari = min(amari, A[i] + A[j])

print((score - (cnt - M) * amari))



import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=list(map(int,input().split()))
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。M個以上になる最大のXを探す
  # [l,r)半開区間
  l,r=0,a[-1]*2+1
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->x~r-1に求めるものがある
    if cnt>=m:
      l=x
    else:# x以上がm個未満ある->l~x-1に求めるものがある
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  print((ans+(m-cnt)*x))

def __starting_point():
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

__starting_point()

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
a_rev = a[::-1]

ok, ng = 1, 200001
while ng-ok > 1:
	x = (ok+ng)//2
	num = 0
	cur = 0
	for i in range(n-1, -1, -1):
		while cur < n and a[i] + a[cur] >= x:
			cur += 1
		num += cur
	if num < m:
		ng = x
	else:
		ok = x
just = ok

ans = 0
larger_cnt = 0
cur = 0

a_cum = [0]
for i in range(n):
	a_cum.append(a_cum[-1] + a[i])

for i in range(n):
	while cur < n and a[i] + a_rev[cur] <= just:
		cur += 1
	larger_cnt += n - cur
	ans += (n - cur) * a[i] + a_cum[n - cur]

ans += just * (m - larger_cnt)
print(ans)

from bisect import bisect_left
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()


def get_count(tot):
    '''
    tot以上を満たす幸福度の握手の個数を数える
    '''
    ret = 0
    for i in range(N):
        cnt = bisect_left(A, tot-A[i])
        ret += N - cnt
    return ret


# 右からの累積和
Asum = A[:]
for i in range(N-2, -1, -1):
    Asum[i] += Asum[i+1]


def get_sum(tot):
    '''
    左端を固定した時の右端の個数分だけ左端を足し、右端の区間和（累積和）も足す。
    '''
    ret = 0
    for i in range(N):
        idx = bisect_left(A, tot-A[i])
        cnt = N - idx
        ret += A[i]*cnt
        # print(idx)
        if idx == N:
            continue
        ret += Asum[idx]
        # print(f'ret = {ret}')
    return ret


# M回握手できる上限を求める
ok = 0
ng = 10**12
while ok + 1 != ng:
    md = (ok + ng)//2
    if M <= get_count(md):
        ok = md
    else:
        ng = md
# print(ok)
# print(get_sum(ok+1))
# print(M - get_count(ok+1))
# print(Asum)
ans = get_sum(ok+1) + (M - get_count(ok+1))*ok

print(ans)


import numpy as np
 
N,M = map(int,input().split())
A = np.array(input().split(),np.int64)
 
A = np.sort(A)
S = np.zeros(N+1,np.int64)
S[1:]= np.cumsum(A)
 
hi = 200001
lo = -1
 
while hi-lo > 1:
    mid = (hi+lo)//2
    above_mid = (N-np.searchsorted(A,mid-A,side='left')).sum()
    if above_mid >= M:
        lo = mid
    else:
        hi = mid
 
X = np.searchsorted(A,hi-A,side='left')
 
above_hi = (N-X).sum()
happiness = (S[-1]-S[X]).sum()
happiness += (A*(N-X)).sum()
happiness += (M-above_hi)*lo
 
print(happiness)

import numpy as np

n, m = list(map(int,input().split()))
a = list(map(int,input().split()))

na = np.zeros(2**18)
for i in a:
    na[i] += 1

fa = np.fft.fft(na)

c = np.round(np.fft.ifft(fa*fa)).astype(int)

ans = 0
cm = 0
for i in range(2**18 - 1, 1, -1):
    cm += c[i]
    ans += i*c[i]
    if cm > m:
        ans -= i * (cm - m)
    if cm >= m:
        break

print(ans)


import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r
from itertools import accumulate

n, m, *a = map(int, sys.stdin.read().split())
a.sort()

def count(border):
  res = 0
  for x in a:
    b = border - x
    res += n - bi_l(a, b)
  return res

def main():
  lo, hi = 1, a[-1] * 2 + 1
  while lo + 1 < hi:
    border = (lo + hi) // 2
    if count(border) >= m:
      lo = border
    else:
      hi = border
  
  s = a.copy() + [0]
  *s, = accumulate(s[::-1])
  tot = 0
  for x in a:
    b = lo - x
    c = n - bi_l(a, b)
    tot += x * c + s[c]
  
  tot -= lo * (count(lo) - m)
  print(tot)

def __starting_point():
  main()
__starting_point()

from bisect import bisect_left as BL 
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()

#border以上の幸福度を返す握手の組の数が、M以上であるか
def isok(border):
  res=0
  for i in range(N):
    res+=N-BL(A,border-A[i])
  return res>=M
    

ok=0
ng=A[-1]*2+1
mid=(ok+ng)//2

#幸福度h以上の握手がM組以上存在するような最大のhを探す
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if isok(mid):
    ok=mid
  else:
    ng=mid
  
B=reversed(A)
SB=[0]
for b in B:
  SB.append(b+SB[-1])
  
ans=0
shake_c=0
for i in range(N):
  goodshake=N-BL(A,ok-A[i])
  shake_c+=goodshake
  ans+=A[i]*goodshake
  ans+=SB[goodshake]  
ans-=(shake_c-M)*ok
print(ans)