Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid

   else:
      right = mid

acc = a
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

Fixed submission:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
   else:
      right = mid

acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

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

def binary_search(y):
   left_index=-1
   right_index=len(A)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if A[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in A:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

#print(X[left_index_2])
happiness=0
count_2=0
for a in A:
   y=X[left_index_2]-a
   z=binary_search(y)
   #print(z)
   happiness+=sum(A[0:z])+a*z
   count_2+=z

if count_2>M:
   happiness-=X[left_index_2]*(count_2-M)
print(happiness)

Fixed submission:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
   else:
      right = mid

acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

#print(X[left_index_2])
happiness=0
count_2=0
for a in tate:
   y=X[left_index_2]-a
   z=binary_search(y)
   #print(z)
   happiness+=sum(tate[0:z])+a*z
   count_2+=z

while count_2>M:
   happiness-=X[left_index_2]
   count_2-=1
print(happiness)

Fixed submission:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
   else:
      right = mid

acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

#print(X[left_index_2])
happiness=0
count_2=0
for a in tate:
   y=X[left_index_2]-a
   z=binary_search(y)
   #print(z)
   happiness+=sum(tate[0:z])+a*z
   count_2+=z

while count_2>M:
   happiness-=X[left_index_2]
   count_2-=1
print(happiness)

Fixed submission:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
   else:
      right = mid

acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)