import sys

sys.setrecursionlimit(10000000)

# input = sys.stdin.readline

from bisect import *

# from collections import *

# from heapq import *

# import functools

# import itertools

# import math

INF = 500000

MOD = 10**9+7



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

A = [int(x) for x in input().split()]

A.sort()

l, r = 0, 10**6

while l+1 < r:

    m = (l+r)//2

    cnt = 0

    for a in A:

        cnt += N-bisect_left(A, m-a)

    if cnt < M:

        r = m

    else:

        l = m

f = [0]+A[::-1]

for i in range(N):

    f[i+1] += f[i]

cnt, ans = 0, 0

for a in A:

    i = bisect_right(A, l-a)

    ans += f[N-i]+(N-i)*a

    cnt += N-i

print((ans+(M-cnt)*l))

import numpy as np

from numpy.fft import rfft, irfft

import sys

input=sys.stdin.readline



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

fft_len = 1<<18

MAX = 2*10**5

A = np.zeros(fft_len)

for a in [int(x) for x in input().split()]:

    A[a] += 1

F = rfft(A, fft_len)

f = np.rint(irfft(F*F))

n, ans = 0, 0

for i, c in enumerate(f[:MAX+1][::-1]):

    if M < n+c:

        ans += (M-n)*(MAX-i)

        break

    ans += c*(MAX-i)

    n += c

print((int(ans)))

import sys

sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *

# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
MOD = 10**9 + 7
N, M = list(map(int, input().split()))
A = [int(x) for x in input().split()]
A.sort()
l, r = 0, 10**6
while l + 1 < r:
    m = (l + r) // 2
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, m - a)
    if cnt < M:
        r = m
    else:
        l = m
f = [0] + A[::-1]
for i in range(N):
    f[i + 1] += f[i]
cnt, ans = 0, 0
for a in A:
    i = bisect_right(A, l - a)
    ans += f[N - i] + (N - i) * a
    cnt += N - i
print((ans + (M - cnt) * l))

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

input = sys.stdin.readline
N, M = list(map(int, input().split()))
fft_len = 1 << 18
MAX = 2 * 10**5
A = np.zeros(fft_len)
for a in [int(x) for x in input().split()]:
    A[a] += 1
F = rfft(A, fft_len)
f = np.rint(irfft(F * F))
n, ans = 0, 0
for i, c in enumerate(f[: MAX + 1][::-1]):
    if M < n + c:
        ans += (M - n) * (MAX - i)
        break
    ans += c * (MAX - i)
    n += c
print((int(ans)))

+import numpy as np +from numpy.fft import rfft, irfft -sys.setrecursionlimit(10000000) -# input = sys.stdin.readline -from bisect import * - -# from collections import * -# from heapq import * -# import functools -# import itertools -# import math -INF = 500000 -MOD = 10**9 + 7 +input = sys.stdin.readline -A = [int(x) for x in input().split()] -A.sort() -l, r = 0, 10**6 -while l + 1 < r: -    m = (l + r) // 2 -    cnt = 0 -    for a in A: -        cnt += N - bisect_left(A, m - a) -    if cnt < M: -        r = m -    else: -        l = m -f = [0] + A[::-1] -for i in range(N): -    f[i + 1] += f[i] -cnt, ans = 0, 0 -for a in A: -    i = bisect_right(A, l - a) -    ans += f[N - i] + (N - i) * a -    cnt += N - i -print((ans + (M - cnt) * l)) +fft_len = 1 << 18 +MAX = 2 * 10**5 +A = np.zeros(fft_len) +for a in [int(x) for x in input().split()]: +    A[a] += 1 +F = rfft(A, fft_len) +f = np.rint(irfft(F * F)) +n, ans = 0, 0 +for i, c in enumerate(f[: MAX + 1][::-1]): +    if M < n + c: +        ans += (M - n) * (MAX - i) +        break +    ans += c * (MAX - i) +    n += c +print((int(ans)))