Buggy python submission (verdict: Time Limit Exceeded):

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



Fixed submission:

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

Buggy python submission (verdict: Time Limit Exceeded):


# 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 = []
heappush(q,(-2*a[0],0,0))


num = 0
while num < m:
    v,i,j = heappop(q)
    v = -v
    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]),i+1,j))
    if i > j:
        heappush(q,(-(a[i]+a[j+1]),i,j+1))

print(ans)






"""
n,k = [int(i) for i in readline().split()]
r,s,p = [int(i) for i in readline().split()]
t = input()

ans = 0

for i in range(k):
    tt = t[i::k]
    l = len(tt)
    dpr = dps = dpp = 0
    for i in tt:
        if i == "r":
            dpr,dps,dpp = max(dps,dpp),max(dpr,dpp),max(dps,dpr)+p
        if i == "s":
            dpr,dps,dpp = max(dps,dpp)+r,max(dpr,dpp),max(dps,dpr)
        if i == "p":
            dpr,dps,dpp = max(dps,dpp),max(dpr,dpp)+s,max(dps,dpr)

    ans += max(dpr,dps,dpp)


print(ans)
"""

Fixed submission:

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