Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(key=lambda x:-x)

# パワーがi以上の人の数
s = [0 for _ in range(2*a[0]+1)]
for p in a:
    s[p] += 1
for i in range(2*a[0], 0, -1):
    s[i-1] += s[i]

def is_over(x):
    num = 0
    for p in a:
        num += s[max(x-p, 0)]
    return num >= k

ub = 2*a[0]+1
lb = 2*a[-1]
while ub-lb > 1:
    x = (ub+lb)//2
    if is_over(x):
        lb = x
    else:
        ub = x

# a[0]からa[i]の累積和
t = a[:]
for i in range(1, n):
    t[i] += t[i-1]
ans = 0
for p in a:
    # 左手固定
    u = s[max(x-p, 0)] # 握手すると閾値を超えるひとたち
    if u != 0:
        ans += p*u+t[u-1] # 1人目pとu回握手 + 右手はu人までと握手
        k -= u
ans += lb*k # 閾値上の人の処理
print(ans)


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

A.sort(reverse=True)
LB = A[-1] * 2  # 一回の握手で上がる幸福度の下限は、左手も右手もパワーが一番低い人を握った場合
UB = A[0] * 2   # 一回の握手で上がる幸福度の上限は、左手も右手もパワーが一番高い人を握った場合

# cgs[i] は パワーがi以上のゲストの数
cgs = [0] * (UB + 1)
for a in A:
    cgs[a] += 1
for i in range(UB, 0, -1):
    cgs[i - 1] += cgs[i]


# 組み合わせの数がM以上になる一回で発生する幸福度の閾値を二分探索する
def is_ok(n):
    m = 0
    for a in A:
        m += cgs[max(n - a, 0)]
    return m >= M


ok = LB
ng = UB + 1
while ng - ok > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

# cps[i] は A[0]～A[i] の累積和
cps = A[:]
for i in range(1, N):
    cps[i] += cps[i - 1]

result = 0
for a in A:
# 左手固定
    t = cgs[max(ok - a, 0)] # 握手すると閾値を超えるひとたち
    if t != 0:
        result += a * t + cps[t - 1] # 1人目pとu回握手 + 右手はu人までと握手
        M -= t
result += ok * M # 閾値上の人の処理
print(result)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(key=lambda x:-x)

# パワーがi以上の人の数
s = [0 for _ in range(2*a[0]+1)]
for p in a:
    s[p] += 1
for i in range(2*a[0], 0, -1):
    s[i-1] += s[i]

def is_over(x):
    num = 0
    for p in a:
        num += s[max(x-p, 0)]
    return num >= k

ub = 2*a[0]
lb = 2*a[-1]
while ub-lb > 1:
    x = (ub+lb)//2
    if is_over(x):
        lb = x
    else:
        ub = x

# a[0]からa[i]の累積和
t = a[:]
for i in range(1, n):
    t[i] += t[i-1]
ans = 0
for p in a:
    # 左手固定
    u = s[max(x-p, 0)] # 握手すると閾値を超えるひとたち
    if u != 0:
        ans += p*u+t[u-1] # 1人目pとu回握手 + 右手はu人までと握手
        k -= u
ans += lb*k # 閾値上の人の処理
print(ans)


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

A.sort(reverse=True)
LB = A[-1] * 2  # 一回の握手で上がる幸福度の下限は、左手も右手もパワーが一番低い人を握った場合
UB = A[0] * 2   # 一回の握手で上がる幸福度の上限は、左手も右手もパワーが一番高い人を握った場合

# cgs[i] は パワーがi以上のゲストの数
cgs = [0] * (UB + 1)
for a in A:
    cgs[a] += 1
for i in range(UB, 0, -1):
    cgs[i - 1] += cgs[i]


# 組み合わせの数がM以上になる一回で発生する幸福度の閾値を二分探索する
def is_ok(n):
    m = 0
    for a in A:
        m += cgs[max(n - a, 0)]
    return m >= M


ok = LB
ng = UB + 1
while ng - ok > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

# cps[i] は A[0]～A[i] の累積和
cps = A[:]
for i in range(1, N):
    cps[i] += cps[i - 1]

result = 0
for a in A:
# 左手固定
    t = cgs[max(ok - a, 0)] # 握手すると閾値を超えるひとたち
    if t != 0:
        result += a * t + cps[t - 1] # 1人目pとu回握手 + 右手はu人までと握手
        M -= t
result += ok * M # 閾値上の人の処理
print(result)