from itertools import accumulate

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

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

a.sort(reverse=True)

b=[0]*(2*a[0]+1)

for i in range(n):

  b[a[i]]+=1

b=list(accumulate(b[::-1]))[::-1]

s=list(accumulate([0]+a))

ok=0

ng=2*a[0]+1

while ng-ok>1:

  mid=(ng+ok)//2

  cnt=0

  for i in range(n):

    cnt+=b[max(0,mid-a[i])]

  if cnt>=m:

    ok=mid

  else:

    ng=mid

cnt=0

ans=0

for i in range(n):

  t=min(b[max(0,ng-a[i])],m-cnt)

  ans+=s[t]+a[i]*t

  cnt+=t

ans+=(m-cnt)*ok

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

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



A.sort(reverse=True)

LB = A[-1] * 2  # 一回の握手で上がる幸福度の下限は、左手も右手もパワーが一番低い人を握った場合

UB = A[0] * 2   # 一回の握手で上がる幸福度の上限は、左手も右手もパワーが一番高い人を握った場合



# cgs[i] は パワーがi以上のゲストの数

cgs = [0] * (UB + 1)

for a in A:

    cgs[a] += 1

for i in range(UB, 0, -1):

    cgs[i - 1] += cgs[i]





# 組み合わせの数がM以上になる一回で発生する幸福度の閾値を二分探索する

def is_ok(n):

    m = 0

    for a in A:

        m += cgs[max(n - a, 0)]

    return m >= M





ok = LB

ng = UB + 1

while ng - ok > 1:

    m = (ok + ng) // 2

    if is_ok(m):

        ok = m

    else:

        ng = m



# cps[i] は A[0]～A[i] の累積和

cps = A[:]

for i in range(1, N):

    cps[i] += cps[i - 1]



result = 0

for a in A:

    t = cgs[max(ok - a, 0)]

    if t != 0:

        result += a * t + cps[t - 1]

        M -= t

result += ok * M

print(result)

from itertools import accumulate

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0] * (2 * a[0] + 1)
for i in range(n):
    b[a[i]] += 1
b = list(accumulate(b[::-1]))[::-1]
s = list(accumulate([0] + a))
ok = 0
ng = 2 * a[0] + 1
while ng - ok > 1:
    mid = (ng + ok) // 2
    cnt = 0
    for i in range(n):
        cnt += b[max(0, mid - a[i])]
    if cnt >= m:
        ok = mid
    else:
        ng = mid
cnt = 0
ans = 0
for i in range(n):
    t = min(b[max(0, ng - a[i])], m - cnt)
    ans += s[t] + a[i] * t
    cnt += t
ans += (m - cnt) * ok
print(ans)

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
LB = A[-1] * 2  # 一回の握手で上がる幸福度の下限は、左手も右手もパワーが一番低い人を握った場合
UB = A[0] * 2  # 一回の握手で上がる幸福度の上限は、左手も右手もパワーが一番高い人を握った場合
# cgs[i] は パワーがi以上のゲストの数
cgs = [0] * (UB + 1)
for a in A:
    cgs[a] += 1
for i in range(UB, 0, -1):
    cgs[i - 1] += cgs[i]
# 組み合わせの数がM以上になる一回で発生する幸福度の閾値を二分探索する
def is_ok(n):
    m = 0
    for a in A:
        m += cgs[max(n - a, 0)]
    return m >= M


ok = LB
ng = UB + 1
while ng - ok > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m
# cps[i] は A[0]～A[i] の累積和
cps = A[:]
for i in range(1, N):
    cps[i] += cps[i - 1]
result = 0
for a in A:
    t = cgs[max(ok - a, 0)]
    if t != 0:
        result += a * t + cps[t - 1]
        M -= t
result += ok * M
print(result)

-from itertools import accumulate +N, M = list(map(int, input().split())) +A = list(map(int, input().split())) +A.sort(reverse=True) +LB = A[-1] * 2  # 一回の握手で上がる幸福度の下限は、左手も右手もパワーが一番低い人を握った場合 +UB = A[0] * 2  # 一回の握手で上がる幸福度の上限は、左手も右手もパワーが一番高い人を握った場合 +# cgs[i] は パワーがi以上のゲストの数 +cgs = [0] * (UB + 1) +for a in A: +    cgs[a] += 1 +for i in range(UB, 0, -1): +    cgs[i - 1] += cgs[i] +# 組み合わせの数がM以上になる一回で発生する幸福度の閾値を二分探索する +def is_ok(n): +    m = 0 +    for a in A: +        m += cgs[max(n - a, 0)] +    return m >= M -n, m = list(map(int, input().split())) -a = list(map(int, input().split())) -a.sort(reverse=True) -b = [0] * (2 * a[0] + 1) -for i in range(n): -    b[a[i]] += 1 -b = list(accumulate(b[::-1]))[::-1] -s = list(accumulate([0] + a)) -ok = 0 -ng = 2 * a[0] + 1 + +ok = LB +ng = UB + 1 -    mid = (ng + ok) // 2 -    cnt = 0 -    for i in range(n): -        cnt += b[max(0, mid - a[i])] -    if cnt >= m: -        ok = mid +    m = (ok + ng) // 2 +    if is_ok(m): +        ok = m -        ng = mid -cnt = 0 -ans = 0 -for i in range(n): -    t = min(b[max(0, ng - a[i])], m - cnt) -    ans += s[t] + a[i] * t -    cnt += t -ans += (m - cnt) * ok -print(ans) +        ng = m +# cps[i] は A[0]～A[i] の累積和 +cps = A[:] +for i in range(1, N): +    cps[i] += cps[i - 1] +result = 0 +for a in A: +    t = cgs[max(ok - a, 0)] +    if t != 0: +        result += a * t + cps[t - 1] +        M -= t +result += ok * M +print(result)