Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)


Fixed submission:
from bisect import bisect_left

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

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)


Fixed submission:
from bisect import bisect_left

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

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

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

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**12
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

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

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)


Fixed submission:
from bisect import bisect_left

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

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right

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

A.sort()
accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)


Fixed submission:
from bisect import bisect_left

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

def doesOver(k):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, k - a)
    return cnt >= M

overEq = 0
less = A[-1] * 2 + 100

while less - overEq > 1:
    mid = (less + overEq) // 2
    if doesOver(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

ans = 0
cnt = 0
for a in A:
    left = bisect_left(A, overEq - a)
    ans += accA[N] - accA[left]
    ans += (N - left) * a
    cnt += N - left

ans -= (cnt - M) * overEq
print(ans)