import bisect



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

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

A.sort()

B = [0] * N

B[-1] = A[-1]

for i in range(N - 2, -1, -1):

    B[i] = B[i+1]+A[i]





def C(mid):

    tmp = 0

    for a in A:

        pos = bisect.bisect_right(A, mid - a)

        tmp += N-pos

    return tmp > M





lb = 0

rb = 10**6

while rb - lb > 1:

    happy = (lb + rb) // 2

    if C(happy):

        lb = happy

    else:

        rb = happy



ans = 0

cnt = 0

for a in A:

    pos = bisect.bisect_right(A, rb - a)

    if pos == N:

        continue

    ans += B[pos]+(N-pos)*a

    cnt += N - pos

ans += (M-cnt)*rb

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)

import bisect

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


def C(mid):
    tmp = 0
    for a in A:
        pos = bisect.bisect_right(A, mid - a)
        tmp += N - pos
    return tmp > M


lb = 0
rb = 10**6
while rb - lb > 1:
    happy = (lb + rb) // 2
    if C(happy):
        lb = happy
    else:
        rb = happy
ans = 0
cnt = 0
for a in A:
    pos = bisect.bisect_right(A, rb - a)
    if pos == N:
        continue
    ans += B[pos] + (N - pos) * a
    cnt += N - pos
ans += (M - cnt) * rb
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)

-import bisect +import numpy as np -A = list(map(int, input().split())) -A.sort() -B = [0] * N -B[-1] = A[-1] -for i in range(N - 2, -1, -1): -    B[i] = B[i + 1] + A[i] - - -def C(mid): -    tmp = 0 -    for a in A: -        pos = bisect.bisect_right(A, mid - a) -        tmp += N - pos -    return tmp > M - - -lb = 0 -rb = 10**6 -while rb - lb > 1: -    happy = (lb + rb) // 2 -    if C(happy): -        lb = happy -    else: -        rb = happy +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() -cnt = 0 -for a in A: -    pos = bisect.bisect_right(A, rb - a) -    if pos == N: -        continue -    ans += B[pos] + (N - pos) * a -    cnt += N - pos -ans += (M - cnt) * rb +while M > 0: +    h = happy.pop() +    num = cnt.pop() +    num = min(M, num) +    M -= num +    ans += num * h