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

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for k, A in enumerate(As, start=1):
            i = bisect_left(As, x-A)
            num += N-i
            if num >= M:
                return True
            elif num + (N-k)*N < M:
                return False
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


Fixed submission:
from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)

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

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


Fixed submission:
from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)

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

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 10**10+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


Fixed submission:
from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)

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

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 10**10+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


Fixed submission:
from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)