Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

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

scores = [0] * (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
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 sorted(a, reverse=True):
    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)


Fixed submission:
from itertools import accumulate

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

a.sort(reverse=True)
a_acm = list(accumulate(a))

a_cnt = [0] * (10 ** 6 + 1)
for e in a:
    a_cnt[e] += 1

acm = list(accumulate(a_cnt))


def count_handshake(x):
    ret = 0
    for e in a:
        if x - e - 1 >= 0:
            cnt = acm[-1] - acm[x-e-1]
        else:
            cnt = n

        ret += cnt

    return ret


left = 0
right = 10 ** 6

while right - left > 1:
    mid = (left + right) // 2
    if count_handshake(mid) >= m:
        left = mid
    else:
        right = mid

ans = 0
handshake_cnt = 0
for e in a:
    if left - e - 1 >= 0:
        cnt = n - acm[left-e-1]
    else:
        cnt = n

    if cnt > 0:
        ans += e * cnt + a_acm[cnt-1]
        handshake_cnt += cnt

if handshake_cnt > m:
    ans -= left * (handshake_cnt - m)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n, m = 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 c.items():
    for k2, v2 in 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)


Fixed submission:
from itertools import accumulate

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

a.sort(reverse=True)
a_acm = list(accumulate(a))

a_cnt = [0] * (10 ** 6 + 1)
for e in a:
    a_cnt[e] += 1

acm = list(accumulate(a_cnt))


def count_handshake(x):
    ret = 0
    for e in a:
        if x - e - 1 >= 0:
            cnt = acm[-1] - acm[x-e-1]
        else:
            cnt = n

        ret += cnt

    return ret


left = 0
right = 10 ** 6

while right - left > 1:
    mid = (left + right) // 2
    if count_handshake(mid) >= m:
        left = mid
    else:
        right = mid

ans = 0
handshake_cnt = 0
for e in a:
    if left - e - 1 >= 0:
        cnt = n - acm[left-e-1]
    else:
        cnt = n

    if cnt > 0:
        ans += e * cnt + a_acm[cnt-1]
        handshake_cnt += cnt

if handshake_cnt > m:
    ans -= left * (handshake_cnt - m)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n, m = 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 c.items():
    for k2, v2 in 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)


Fixed submission:
from itertools import accumulate

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

a.sort(reverse=True)
a_acm = list(accumulate(a))

a_cnt = [0] * (10 ** 6 + 1)
for e in a:
    a_cnt[e] += 1

acm = list(accumulate(a_cnt))


def count_handshake(x):
    ret = 0
    for e in a:
        if x - e - 1 >= 0:
            cnt = acm[-1] - acm[x-e-1]
        else:
            cnt = n

        ret += cnt

    return ret


left = 0
right = 10 ** 6

while right - left > 1:
    mid = (left + right) // 2
    if count_handshake(mid) >= m:
        left = mid
    else:
        right = mid

ans = 0
handshake_cnt = 0
for e in a:
    if left - e - 1 >= 0:
        cnt = n - acm[left-e-1]
    else:
        cnt = n

    if cnt > 0:
        ans += e * cnt + a_acm[cnt-1]
        handshake_cnt += cnt

if handshake_cnt > m:
    ans -= left * (handshake_cnt - m)

print(ans)