Buggy python submission (verdict: Time Limit Exceeded):
def judge(k, N, A):
    t = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if A[j] + i >= k:
                s = j + 1
                t += j + 1
                break
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in range(N):
        tmp += A[i]
        B.append(tmp)
    r = 0
    tot = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if i + A[j] >= X:
                tot += j + 1
                s = j + 1
                r += i * (j + 1) + B[j]
                break
    return r - (tot - M) * X
print(main())


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def judge(k, N, A):
    t = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if A[j] + i >= k:
                s = j + 1
                t += j + 1
                break
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in range(N):
        tmp += A[i]
        B.append(tmp)
    r = 0
    tot = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if i + A[j] >= X:
                tot += j + 1
                s = j + 1
                r += i * (j + 1) + B[j]
                break
    return r - (tot - M) * X
print(main())


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        im = judge(m - 1, N, A)
        ip = judge(m + 1, N, A)
        if i == M:
            X = m
            break
        if im == M:
            X = m - 1
            break
        if ip == M:
            X = m + 1
            break
        if i > M:
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            if im > M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while True:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if (t >= M and t - p <= M) or t == M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while True:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 1000:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p < M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    for i in range(N):
        for j in range(s):
            if A[i] + A[j] >= m:
                r += A[i] + A[j]
            if A[i] + A[j] < m:
                s = j + 1
                break
    return r - (t - M) * m
    
print(main())
    


Fixed submission:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())