CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
#show_flg=True

ans=0

n,m=LI()
a=sorted(LI())
ra=a[::-1]
##show(a,ra)

def Bigger(x,M): # x以上が M 個以上あるか
    cnt=0
    for i in range(n):
        y=x-ra[i]
        c=bisect.bisect(a,y-1)
        cnt+=n-c
##        show(x,a[i],y,cnt)
        if cnt>=M:
            return True
    return False

# function to check if x satisfies the condition
def check(x):
    if x==condition:
        rt=True
    else:
        rt=False
    return rt

# initial value
ng=1+a[-1]+a[-1]
ok=-1

while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if Bigger(mid,m):
        ok=mid
    else:
        ng=mid

mean=ok
##show('ok=',ok,m)
# [ ok | ng ] is the boundary of the condition

##show(Bigger(67,3))

choice=0
for i in range(n):
    num=n-bisect.bisect(a,mean-a[i]-1)
    choice+=num
    ans+=num*a[i]*2
##    show('i,a[i],num,choice',i,a[i],num,choice)
##show('ans=')
#print(ans)
print(ans-mean*(choice-m))


# Optimized solution
from bisect import bisect as B
LI=lambda:list(map(int,input().split()))
A=0
n,m=LI()
a=sorted(LI())
ra=a[::-1]
def Q(x,M):
    w=0
    for i in range(n):
        y=x-ra[i]
        c=B(a,y-1)
        w+=n-c
        if w>=M:return True
    return False
N=a[-1]*3
O=-1
while abs(O-N)>1:
    f=(O+N)//2
    if Q(f,m):
        O=f
    else:
        N=f
O
P=0
for i in range(n):
    e=n-B(a,O-a[i]-1)
    P+=e
    A+=e*a[i]*2
print((A-O*(P-m)))
# Original solution
from bisect import bisect as B
LI=lambda:list(map(int,input().split()))
A=0
n,m=LI()
a=sorted(LI())
ra=a[::-1]
def Q(x,M):
    w=0
    for i in range(n):
        y=x-ra[i]
        c=B(a,y-1)
        w+=n-c
        if w>=M:return True
    return False
N=a[-1]*3
O=-1
while abs(O-N)>1:
    f=(O+N)//2
    if Q(f,m):
        O=f
    else:
        N=f
O
P=0
for i in range(n):
    e=n-B(a,O-a[i]-1)
    P+=e
    A+=e*a[i]*2
print((A-O*(P-m)))


# Optimized solution
from bisect import bisect as B
LI=lambda:list(map(int,input().split()))
A=0
n,m=LI()
a=sorted(LI())
R=a[::-1]
def Q(x,M):
    w=0
    for i in range(n):
        y=x-R[i]
        c=B(a,y-1)
        w+=n-c
        if w>=M:return True
    return False
N=a[-1]*3
O=-1
while N-O>1:
    f=(O+N)//2
    if Q(f,m):
        O=f
    else:
        N=f
P=0
for i in range(n):
    e=n-B(a,O-a[i]-1)
    P+=e
    A+=e*a[i]*2
print((A-O*(P-m)))
# Original solution
import bisect
LI=lambda:list(map(int,input().split()))
A=0
n,m=LI()
a=sorted(LI())
R=a[::-1]
def Q(x,M):
    w=0
    for i in range(n):
        y=x-R[i]
        c=bisect.bisect(a,y-1)
        w+=n-c
        if w>=M:return True
    return False
N=a[-1]*3
O=-1
while N-O>1:
    f=(O+N)//2
    if Q(f,m):
        O=f
    else:
        N=f
P=0
for i in range(n):
    e=n-bisect.bisect(a,O-a[i]-1)
    P+=e
    A+=e*a[i]*2
print((A-O*(P-m)))


# Optimized solution
from bisect import bisect as B
LI=lambda:list(map(int,input().split()))
A=0
n,m=LI()
a=sorted(LI())
R=a[::-1]
def Q(x,M):
  w=0
  for i in range(n):
    y=x-R[i]
    c=B(a,y-1)
    w+=n-c
    if w>=M:return 1
  return 0
N=a[-1]*3
O=-1
while N-O>1:
  f=(O+N)//2
  if Q(f,m):O=f
  else:N=f
P=0
for i in range(n):
  e=n-B(a,O-a[i]-1)
  P+=e
  A+=e*a[i]*2
print((A-O*(P-m)))
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl())
ng = 10**9+1
ok = -1
def sol(x):
    cnt = 0
    for i,t in enumerate(a):
        tmp = x - t
        c = bisect.bisect_left(a,tmp)
        cnt += n-c
    return True if cnt >= m else False

while ng-ok > 1:
    mid = (ng+ok)//2
    if sol(mid):
        ok = mid
    else: ng = mid
    # print(ok,ng)
# print(ok)
res = 0
cnt = 0
revc = [0]
for i in range(n)[::-1]:
    revc.append(revc[-1] + a[i])
# print(revc)
for i in range(n):
    j = n-bisect.bisect_left(a,ok-a[i])
    res += j*a[i] + revc[j]
    cnt += j
res -= (cnt-m) * ok
print(res)

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl(); a.sort()
ok = a[0] + a[0] - 1
ng = a[-1] + a[-1] + 1
def sol(x):
    res = 0
    for i in range(n):
        y = x-a[i]
        res += n-bisect_left(a,y)
    return True if res >= m else False
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if sol(mid):
        ok = mid
    else:
        ng = mid
b = [0]
for i in range(n)[::-1]:
    b.append(b[-1]+a[i])
res = 0
cnt = 0
# print(b,ok)
for x in a:
    ind = n-bisect_left(a,ok-x)
    cnt += ind
    res += b[ind] + x*ind
print((res-(cnt-m)*ok))
# Original solution
from bisect import bisect_left, bisect_right

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

# ll = []
# for i in A:
#     for j in A:
#         ll.append(i+j)
# ll.sort()

def f(x):
    v = 0
    for i in A:
        v += N-bisect_right(A, x-i)
    return v

def get_nearest(l):
    ans = 10**12
    for i in A:
        res = bisect_right(A, l-i)
        if 0<=res<N:
            ans = min(ans, A[res]+i)
    return ans

l, r = 0, 10**12+1
while r-l>1:
    m = (l+r)//2
    if f(m)>=M:
        l = m
    else:
        r = m

ans = 0
for i in A:
    v1 = N-bisect_right(A, r-i)
    ans += ac[N]-ac[N-v1]+v1*i
ans += (M-f(r))*get_nearest(l)

print(ans)

# Optimized solution
from bisect import bisect_right

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

def f(x):
    v = 0
    for i in A:
        v += N-bisect_right(A, x-i)
    return v

def g(l):
    ans = INF
    for i in A:
        res = bisect_right(A, l-i)
        if 0<=res<N:
            ans = min(ans, A[res]+i)
    return ans

l, r = 0, INF+1
while r-l>1:
    m = (l+r)//2
    if f(m)>=M:
        l = m
    else:
        r = m

ans = 0
for i in A:
    v1 = N-bisect_right(A, r-i)
    ans += ac[N]-ac[N-v1]+v1*i
ans += (M-f(r))*g(l)

print(ans)
# Original solution
n,m=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
import bisect
# 解説の二分探索
# あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になるXを探す
l,r=0,a[-1]*2
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を増加
  [l,r]=[x,r] if cnt>=m else [l,x]
x=(l+r)//2
ans=[]
for ai in a:
  bi=bisect.bisect_left(a,x-ai)
  ans.extend([aj+ai for aj in a[bi:]])
ans.sort()
print((sum(ans[-m:])))


# Optimized solution

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))

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
# Original solution
from bisect import bisect_left


def check(x, m):
    # 幸福度が x 以上となる握手が m 通り以上か
    cnt = 0
    for i in range(N):
        y = x - A[i]
        p = bisect_left(A, y)
        cnt += N - p
    return cnt >= m


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

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

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

X = ok
ans = 0
cnt = 0
amari = 2 * 10 ** 5 + 1
for i in range(N):
    Aj = X - A[i]
    j = bisect_left(A, Aj)
    ans += S[N] - S[j] + A[i] * (N - j)
    cnt += N - j
    if j < N:
        amari = min(amari, A[i] + A[j])

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


# Optimized solution
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))
# Original solution
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    cor_v = -1
    inc_v = 10 ** 20
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in a:
            cost += n - bisect.bisect_left(a, bin_v - v)
            if cost > m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = [0] + list(itertools.accumulate(a))
    c = 0
    t = 0
    for v in a:
        p = bisect.bisect_left(a, cor_v - v)
        c += n - p
        t += acm[-1] - acm[p] + v * (n - p)
    print((t - (c - m) * cor_v))


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    cor_v = -1
    inc_v = 10 ** 11
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in a:
            cost += n - bisect.bisect_left(a, bin_v - v)
            if cost > m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = [0] + list(itertools.accumulate(a))
    c = 0
    t = 0
    for v in a:
        p = bisect.bisect_left(a, cor_v - v)
        c += n - p
        t += acm[-1] - acm[p] + v * (n - p)
    print((t - (c - m) * cor_v))


if __name__ == '__main__':
    solve()
# Original solution
#python3
INF = int(1e9)

def main():
    n, m = list(map(int, input().split()))
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()

# Optimized solution

INF = int(1e9)

def main():
    n, m = list(map(int, input().split()))
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()
# Original solution
import bisect

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

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

def solve(min_power):
    ans = 0
    for pos in range(n):
        tmp = min_power - a[pos]
        next_pos = bisect.bisect_left(a[pos:], tmp)
        times = n - pos - next_pos
        if times == n - pos:
            ans += 2 * (times - 1) + 1 
        else:
            ans += 2 * times
    if ans >= m:
        return True
    else:
        return False

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

cnt = 0
ans = 0

for pos in range(n):
    tmp = ok - a[pos]
    next_pos = bisect.bisect_left(a[pos:], tmp)
    times = n - pos - next_pos
    if times == n - pos:
        cnt += 2 * (times - 1) + 1 
        ans += 2 * (ruiseki[n] - ruiseki[n-times+1] + (times-1)*a[pos]) + 2*a[pos]
    else:
        cnt += 2 * times
        ans += 2 * (ruiseki[n] - ruiseki[n-times] + (times)*a[pos])

print((ans - (cnt-m)*ok))

# Optimized solution
import bisect


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

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

def solve(min_power):
    ans = 0
    for pos in range(n):
        tmp = min_power - a[pos]
        next_pos = max(bisect.bisect_left(a, tmp), pos)
        times = n - pos - (next_pos - pos)
        if times == n - pos:
            ans += 2 * (times - 1) + 1 
        else:
            ans += 2 * times
    if ans >= m:
        return True
    else:
        return False

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

cnt = 0
ans = 0

for pos in range(n):
    tmp = ok - a[pos]
    next_pos = max(bisect.bisect_left(a, tmp), pos)
    times = n - pos - (next_pos - pos)
    if times == n - pos:
        cnt += 2 * (times - 1) + 1 
        ans += 2 * (ruiseki[n] - ruiseki[n-times+1] + (times-1)*a[pos]) + 2*a[pos]
    else:
        cnt += 2 * times
        ans += 2 * (ruiseki[n] - ruiseki[n-times] + times*a[pos])

print((ans - (cnt-m)*ok))
# Original solution
import bisect


def solve(mid):
    cnt = 0
    r = n
    for i in range(n):
        l = bisect.bisect_left(a, mid - a[i])
        cnt += (r - l)
    return cnt >= m
    

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

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

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

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.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)


# Optimized solution
import bisect


def solve(mid):
    cnt = 0
    l = n
    r = n
    for i in range(n):
        while True:
            if l == 0:
                break
            if a[l - 1] < mid - 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 = sorted(a)

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

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

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.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)
# Original solution
from sys import stdin
f_i = stdin

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

A.sort()

from bisect import bisect_left

def shake_count(power):
    return N ** 2 - sum(bisect_left(A, power - left_hand) for left_hand in A)

lower = A[0] * 2 - 1
upper = A[-1] * 2 + 1
while lower + 1 < upper:
    mid = (lower + upper) // 2
    if shake_count(mid) >= M:
        lower = mid
    else:
        upper = mid

ans = 0
for left_hand in A:
    idx = bisect_left(A, upper - left_hand)
    ans += sum(A[idx:]) + left_hand * (N - idx)

ans += lower * (M - shake_count(upper))

print(ans)

# Optimized solution
from sys import stdin
f_i = stdin

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

A.sort()

from bisect import bisect_left

def shake_count(power):
    return N ** 2 - sum(bisect_left(A, power - left_hand) for left_hand in A)

lower = A[0] * 2 - 1
upper = A[-1] * 2 + 1
while lower + 1 < upper:
    mid = (lower + upper) // 2
    if shake_count(mid) >= M:
        lower = mid
    else:
        upper = mid

X = tuple(bisect_left(A, upper - left_hand) for left_hand in A)

from itertools import accumulate
acc = tuple(accumulate([0] + A))

s = acc[-1]
ans = sum(s - acc[x] for x in X) + sum(a * (N - x) for a, x in zip(A, X))

rest_shake_count = M - (N ** 2 - sum(X))
ans += lower * rest_shake_count

print(ans)
# Original solution
from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = 0
H = sum(a) ** 2 + 1

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print((ans - (count-m) * L))


# Optimized solution
from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = a[-1] * 2
H = a[0] * 2

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print((ans - (count-m) * L))
# Original solution
import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

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

def calX(a,n,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(a,n,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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]

x = calX(a,n,m,a[0]*2,a[n-1]*2)

out = 0
for i in range(n):
	idx = bisect_left(a,x-a[i])
	out += s[n]-s[idx]+a[i]*(n-idx)

out -= (isOver(a,n,x)-m)*x

print(out)

# Optimized solution
import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

def isOver(A,n,x):
	cnt = 0
	for a in A:
		cnt += n-bisect_left(A,x-a)
	return cnt

def calOut(A,s,n,x):
	out = 0
	for a in A:
		idx = bisect_left(A,x-a)
		out += s[n]-s[idx]+a*(n-idx)
	return out - (isOver(A,n,x)-m)*x

def calX(A,n,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(A,n,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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]

x = calX(A,n,m,A[0]*2,A[n-1]*2)

print((calOut(A,S,n,x)))