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

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

A.sort(reverse=True)



#幸福度をX以上増やせる手が何通りあるか？を二分探索．

#左手で握る人は線形探索，右手が二分探索で探す

#最後は累積和で計算



inf = 2*10**5+1

X_top = inf

X_bot = 0 #M手以上の組み合わせが作れる最大値



#幸福度をX以上挙げられる手の通り数ががMになる境界を探す

while X_top - X_bot !=1:  

    X=(X_top+X_bot)//2

    num=0

    

    for i in range(N):

        ok=-1

        ng=N

        h1=A[i]

        

        #右手と左手の合計がXになる境界を探す

        while ng-ok!=1:

            med=(ok+ng)//2

            h2=A[med]

            if h1+h2>=X:

                ok=med

            else:

                ng=med

        num+=ok+1

    

    if num>=M:

        X_bot = X

    else:

        X_top = X

        

ok_list=[0]*N

#各左手に対して何個okなくみがあるか探す

for i in range(N):

        ok=-1

        ng=N

        h1=A[i]

        X = X_bot

        #右手と左手の合計がXになる境界を探す

        while ng-ok!=1:

            med=(ok+ng)//2

            h2=A[med]

            if h1+h2>=X:

                ok=med

            else:

                ng=med

        ok_list[i]=ok



S=[0]*(N+1)

for i in range(N):

    S[i+1]=S[i]+A[i]



ans=0

for i in range(N):

    ans += A[i]*(ok_list[i]+1)+S[ok_list[i]+1]



if sum(ok_list)+N>M:

    ans-=(sum(ok_list)+N-M)*X

print(ans)
import numpy as np



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

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

Amax=max(A)



n0 = 2**int(np.ceil(np.log2(2*Amax+1)))#Amax+1以上となる最小の2のべき乗数



Afre=np.zeros(n0).astype(int)#パワーの頻度(1~Amax+1)

for i in range(N):

    Afre[A[i]]+=1



#astype(int)は切り捨てなので，rintで四捨五入してから．

S = np.rint(np.fft.irfft(np.fft.rfft(Afre)*np.fft.rfft(Afre))).astype(int)

Scum =S.cumsum()#累積和

bd = N*N-M#上からM個を取り出したい

i=np.searchsorted(Scum,bd)#価値iを生み出せる組みがM個以上ある

#価値iが生み出せる選び方の余分なものを引きたい

remove=((Scum[-1]-Scum[i])-M)*i

ans=0

for j in range(i+1,n0):

    ans+=S[j]*j

print((ans-remove))
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
# 幸福度をX以上増やせる手が何通りあるか？を二分探索．
# 左手で握る人は線形探索，右手が二分探索で探す
# 最後は累積和で計算
inf = 2 * 10**5 + 1
X_top = inf
X_bot = 0  # M手以上の組み合わせが作れる最大値
# 幸福度をX以上挙げられる手の通り数ががMになる境界を探す
while X_top - X_bot != 1:
    X = (X_top + X_bot) // 2
    num = 0
    for i in range(N):
        ok = -1
        ng = N
        h1 = A[i]
        # 右手と左手の合計がXになる境界を探す
        while ng - ok != 1:
            med = (ok + ng) // 2
            h2 = A[med]
            if h1 + h2 >= X:
                ok = med
            else:
                ng = med
        num += ok + 1
    if num >= M:
        X_bot = X
    else:
        X_top = X
ok_list = [0] * N
# 各左手に対して何個okなくみがあるか探す
for i in range(N):
    ok = -1
    ng = N
    h1 = A[i]
    X = X_bot
    # 右手と左手の合計がXになる境界を探す
    while ng - ok != 1:
        med = (ok + ng) // 2
        h2 = A[med]
        if h1 + h2 >= X:
            ok = med
        else:
            ng = med
    ok_list[i] = ok
S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + A[i]
ans = 0
for i in range(N):
    ans += A[i] * (ok_list[i] + 1) + S[ok_list[i] + 1]
if sum(ok_list) + N > M:
    ans -= (sum(ok_list) + N - M) * X
print(ans)

import numpy as np

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
Amax = max(A)
n0 = 2 ** int(np.ceil(np.log2(2 * Amax + 1)))  # Amax+1以上となる最小の2のべき乗数
Afre = np.zeros(n0).astype(int)  # パワーの頻度(1~Amax+1)
for i in range(N):
    Afre[A[i]] += 1
# astype(int)は切り捨てなので，rintで四捨五入してから．
S = np.rint(np.fft.irfft(np.fft.rfft(Afre) * np.fft.rfft(Afre))).astype(int)
Scum = S.cumsum()  # 累積和
bd = N * N - M  # 上からM個を取り出したい
i = np.searchsorted(Scum, bd)  # 価値iを生み出せる組みがM個以上ある
# 価値iが生み出せる選び方の余分なものを引きたい
remove = ((Scum[-1] - Scum[i]) - M) * i
ans = 0
for j in range(i + 1, n0):
    ans += S[j] * j
print((ans - remove))

+import numpy as np + -A.sort(reverse=True) -# 幸福度をX以上増やせる手が何通りあるか？を二分探索． -# 左手で握る人は線形探索，右手が二分探索で探す -# 最後は累積和で計算 -inf = 2 * 10**5 + 1 -X_top = inf -X_bot = 0  # M手以上の組み合わせが作れる最大値 -# 幸福度をX以上挙げられる手の通り数ががMになる境界を探す -while X_top - X_bot != 1: -    X = (X_top + X_bot) // 2 -    num = 0 -    for i in range(N): -        ok = -1 -        ng = N -        h1 = A[i] -        # 右手と左手の合計がXになる境界を探す -        while ng - ok != 1: -            med = (ok + ng) // 2 -            h2 = A[med] -            if h1 + h2 >= X: -                ok = med -            else: -                ng = med -        num += ok + 1 -    if num >= M: -        X_bot = X -    else: -        X_top = X -ok_list = [0] * N -# 各左手に対して何個okなくみがあるか探す +Amax = max(A) +n0 = 2 ** int(np.ceil(np.log2(2 * Amax + 1)))  # Amax+1以上となる最小の2のべき乗数 +Afre = np.zeros(n0).astype(int)  # パワーの頻度(1~Amax+1) -    ok = -1 -    ng = N -    h1 = A[i] -    X = X_bot -    # 右手と左手の合計がXになる境界を探す -    while ng - ok != 1: -        med = (ok + ng) // 2 -        h2 = A[med] -        if h1 + h2 >= X: -            ok = med -        else: -            ng = med -    ok_list[i] = ok -S = [0] * (N + 1) -for i in range(N): -    S[i + 1] = S[i] + A[i] +    Afre[A[i]] += 1 +# astype(int)は切り捨てなので，rintで四捨五入してから． +S = np.rint(np.fft.irfft(np.fft.rfft(Afre) * np.fft.rfft(Afre))).astype(int) +Scum = S.cumsum()  # 累積和 +bd = N * N - M  # 上からM個を取り出したい +i = np.searchsorted(Scum, bd)  # 価値iを生み出せる組みがM個以上ある +# 価値iが生み出せる選び方の余分なものを引きたい +remove = ((Scum[-1] - Scum[i]) - M) * i -for i in range(N): -    ans += A[i] * (ok_list[i] + 1) + S[ok_list[i] + 1] -if sum(ok_list) + N > M: -    ans -= (sum(ok_list) + N - M) * X -print(ans) +for j in range(i + 1, n0): +    ans += S[j] * j +print((ans - remove))