Buggy python submission (verdict: Runtime Error):
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#C[i]=パワーがi以下の人数
C=[0]*(10**5+1)
for a in A:
    C[a]+=1
for i in range(1,len(C)):
    C[i]+=C[i-1]

#和がx以上になる組み合わせの総数を求める関数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        p+=(N-(C[x-a-1] if x-a-1>=0 else 0))
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**5*2+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=[0]+list(reversed(A[:]))
for i in range(1,N+1):
    S[i]+=S[i-1]
ans=0
for a in A:
    idx=bisect.bisect_left(A,r-a)
    ans+=a*(N-idx) + S[N-idx]
    M-=(N-idx)

#回数のあまり分lを足す
ans+=l*M

print(ans)

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

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

#回数のあまり分lを足す
ans+=l*M

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

#回数のあまり分lを足す
ans+=l*M

print(ans)

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

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

#回数のあまり分lを足す
ans+=l*M

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
N,M=map(int,input().split())
A=list(map(int,input().split()))

S=sorted([sum(t) for t in product(A,A)],reverse=True)
print(sum(S[:M]))


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

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

#回数のあまり分lを足す
ans+=l*M

print(ans)