CodeEff/ECCO huggingface dataset:
# Original solution
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 10871635969, 7
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

# Optimized solution
k = 34
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(len(B)*2-1)]]

N, M = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = li(st(nu(B) ** 2))
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)
# Original solution
A = [1] * (1<<18)
B = [1] * (1<<18)
def convolve(a, b):
    def fft(f, w, p):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d]
                    f[j] = (x + y) % p
                    f[j+d] = u * (x - y) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f, w, p):
        d = 1
        while d < n:
            v = pow(w, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d] * u
                    f[j] = (x + y) % p
                    f[j+d] = (x - y) % p
                u = u * v % p
            d *= 2
 
    p, g = (81 << 27) + 1, 7
    n0, n1 = len(a), len(b)
    n = 1 << ((max(n0, n1) - 1).bit_length() + 1)
    a = a[:] + [0] * (n-n0)
    b = b[:] + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    fft(a, w, p)
    fft(b, w, p)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a, pow(w, p - 2, p), p)
    invn = pow(n, p - 2, p)
    for i in range(n0 + n1 - 1):
        a[i] = a[i] * invn % p
    return a

N, M = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

# Optimized solution
k = 34
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(len(B)*2-1)]]

N, M = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = li(st(nu(B) ** 2))
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)
# Original solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 10**9 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**9 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)


# Optimized solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**5 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)
# Original solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**5 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)


# Optimized solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)
# Original solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)


# Optimized solution
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 2*(10**5)+1 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    if (n - bisect.bisect_left(reva,tgt-reva[n-1]))*n < M:
        return False
    for i in range(n):
        res += n - bisect.bisect_left(reva,tgt-reva[n-i-1])
        if M <= res:
            return True
    return False

N,M = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)
# Original solution

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

a.sort(reverse=True)

from heapq import *

ans = 0
q = []
cc = 10**12
c = 10**6

heappush(q,(-2*a[0]*cc))


num = 0
while num < m:
    v = heappop(q)
    v = -v
    v,i,j = v//cc, (v%cc)//c, v%c

    ans += v
    num += 1
    if i != j:
        if num < m:
            num += 1
            ans += v
        else:
            break
        
    #print(v,i,j,num)
    if j == 0 and i < n-1:
        
        heappush(q,-(a[i+1]+a[j])*cc-(i+1)*c-j)
    if i > j:
        heappush(q,-(a[i]+a[j+1])*cc-i*c-(j+1))

print(ans)



# Optimized solution

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

#a.sort(reverse=True)

a.sort()



def check(mid):
    num = 0
    p = 0
    for i in range(n-1,-1,-1):
        c = 0
        while p<n and a[p]+a[i] < mid:
            p += 1
        num += n-p
    #print(mid,num,"mn")
    return num


ok = a[0]*2-1
ng = a[-1]*2+1

while ng - ok > 1:
    mid = (ng+ok)//2
    c = check(mid)
    if c<m:
        ng = mid
    else:
        ok = mid
    
    #print(ok,ng)
    
#print(ok)
    



ans = 0
p = n-1
num = 0

res = [0]*n
for i in range(n):
    c = 0
    while p>=0 and a[p]+a[i] >= ng:
        p -= 1
    res[i] = n-1-p
    num += n-1-p

for i in range(n):
    ans += res[i]*a[i]
ans *= 2
#print(ans,num)
print((ans+ok*(m-num)))
# Original solution
from collections import Counter

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
MAX = 10 ** 5

c = Counter(a)
scores = [0] * (2 * MAX + 1)

for k1, v1 in list(c.items()):
    for k2, v2 in list(c.items()):
        scores[k1 + k2] += v1 * v2

ans = 0
for i, e in enumerate(scores[::-1]):
    point = 2 * MAX - i
    cnt = min(e, m)
    ans += point * cnt
    m -= cnt

print(ans)


# Optimized solution
from itertools import accumulate

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
MAX = 10 ** 5

scores = [0] * (2 * MAX + 1)
for e in a:
    scores[e] += 1

acc = list(accumulate(scores))


def f(x):
    cnt = 0
    for e in a:
        cnt += n - acc[max(0, x - e - 1)]

    return cnt


l = 0
r = 2 * MAX + 1
while r - l > 1:
    mid = (l + r) // 2
    if f(mid) >= m:
        l = mid
    else:
        r = mid

scores_sum = [i * e for i, e in enumerate(scores)]
acc_sum = list(accumulate(scores_sum))
sm = sum(a)
ans = 0
cnt_sum = 0
for e in a:
    i = max(0, l - e - 1)
    cnt = n - acc[i]
    ans += e * cnt + sm - acc_sum[i]
    cnt_sum += cnt

ans -= (cnt_sum - m) * l

print(ans)
# Original solution
import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x,n):
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 10**10+2
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx,n) < m:
        rx = mx
    elif hsnum(a,mx,n) > m:
        if hsnum(a,mx+1,n) < m:
            error = hsnum(a,mx,n)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
ans = 0
for i in range(n):
    rema = lx - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]+suma[n]-suma[j]
print((ans-error*lx))

# Optimized solution
import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x,n):
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 2*10**5+2
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx,n) < m:
        rx = mx
    elif hsnum(a,mx,n) > m:
        if hsnum(a,mx+1,n) < m:
            error = hsnum(a,mx,n)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
ans = 0
for i in range(n):
    rema = lx - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]+suma[n]-suma[j]
print((ans-error*lx))
# Original solution
def main():
    import bisect
    import sys
    from itertools import accumulate
    input = sys.stdin.readline
    def hsnum(ls,x,n):
        num = 0
        for i in range(n):
            y = x-ls[i]
            num += n-bisect.bisect_left(ls,y)
        return num
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    a = tuple(a)
    suma = [0]+list(accumulate(a))
    lx = 0
    rx = 2*10**5+2
    error = 0
    while lx < rx:
        mx = (lx+rx)//2
        if hsnum(a,mx,n) < m:
            rx = mx
        elif hsnum(a,mx,n) > m:
            if hsnum(a,mx+1,n) < m:
                error = hsnum(a,mx,n)-m
                lx = mx
                break
            lx = mx + 1
        else:
            lx = mx
            break
    ans = 0
    for i in range(n):
        rema = lx - a[i]
        j = bisect.bisect_left(a,rema)
        ans += (n-j)*a[i]+suma[n]-suma[j]
    print((ans-error*lx))
if __name__ == "__main__":
    main()

# Optimized solution
def main():
    import bisect
    import sys
    from itertools import accumulate
    input = sys.stdin.readline
    def hsnum(ls,x):
        num = 0
        for i in range(n):
            y = x-ls[i]
            num += n-bisect.bisect_left(ls,y)
        return num
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    suma = [0]+list(accumulate(a))
    lx = 0
    rx = 2*10**5+2
    error = 0
    while lx < rx:
        mx = (lx+rx)//2
        if hsnum(a,mx) < m:
            rx = mx
        elif hsnum(a,mx) > m:
            if hsnum(a,mx+1) < m:
                error = hsnum(a,mx)-m
                lx = mx
                break
            lx = mx + 1
        else:
            lx = mx
            break
    ans = 0
    for i in range(n):
        rema = lx - a[i]
        j = bisect.bisect_left(a,rema)
        ans += (n-j)*a[i]+suma[n]-suma[j]
    print((ans-error*lx))
if __name__ == "__main__":
    main()
# Original solution
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*110000
a_sum = [0]*110000

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        case += n-bisect_right(a,x-a[i]-1)
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

# Optimized solution
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*100010
a_sum = [0]*100010

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,-1,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if 0<= x-a[i]<= 10**5+5:
            case += a_count[x-a[i]]
        elif x-a[i] < 0:
            case += n
    if case >= m:
        ch = True
    else:
        ch = False
    return ch

l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)
# Original solution
import bisect

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print((ans - (count-M)*surplus))

# Optimized solution
import bisect


N, M = list(map(int, input().split()))
Al = list(map(int, input().split()))
Al.sort() # 左手で握手する人のリスト
Ar = Al.copy()[::-1] # 右手で握手する人のリスト

def count_large_2(L1, L2, x):
  # L1.sort()
  # L2.sort(reverse=True)
  N1, N2 = len(L1), len(L2)
  i = j = 0
  c = 0
  while i<N1 and j<N2:
    if L1[i]+L2[j] >= x:
      c += 1
      j += 1
      if j >= N2:
        c += (N1-i-1) * N2
    else:
      i += 1
      if i>=N1:
        continue
      c += j
  return c

left = 0 # True
right = Al[-1]*2 + 1 # False
while left+1 < right:
  mid = (left + right) // 2
  if count_large_2(Al, Ar, mid) >= M:
    left = mid
  else:
    right = mid


x = left
accum_A = [Ar[0]]
for i, a in enumerate(Ar):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
surplus = 2*10**5
for ai in Ar:
  idx = bisect.bisect_left(Al, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+Al[idx])
 
 
print((ans - (count-M)*surplus))
# Original solution
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=list(map(int,input().split()))
A=sorted(map(int,input().split()))
left,right=-1,10**20
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)
    cnt+=N-b
    ans+=r[N]-r[b]
print((ans-D*(cnt-M)))


# Optimized solution
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=list(map(int,input().split()))
A=sorted(map(int,input().split()))
left,right=-1,(10**5)*2+1
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)+(r[N]-r[b])
    cnt+=N-b
print((ans-D*(cnt-M)))