Problem:
Takahashi has come to a party as a special guest. There are N ordinary guests at the party. The i-th ordinary guest has a _power_ of A_i.  Takahashi has decided to perform M _handshakes_ to increase the _happiness_ of the party (let the current happiness be 0). A handshake will be performed as follows:    * Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).   * Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.  However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:    * Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).  What is the maximum possible happiness after M handshakes?

Incorrect submission (verdict: Wrong Answer):
def solve(n, m, a) -> int:
    from bisect import bisect_left, bisect_right
    from itertools import accumulate
    from collections import Counter

    *a, = sorted(a)
    acc = (0,) + tuple(accumulate(a))

    c = Counter(a)

    def is_ok(h):
        ret = 0
        for i, x in enumerate(a):
            j = bisect_left(a, h - x)
            ret += (n - j) * 2
            if ret >= m * 2:
                return True
        return False

    def binary_search():
        ok = 0
        ng = a[-1] * 2 + 1  
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    min_pair_happiness = binary_search()

    ret = 0
    for i, x in enumerate(a):
        j = bisect_left(a, min_pair_happiness - x)
        k = bisect_right(a, min_pair_happiness - x)
        ret += (n - j) * x + (acc[n] - acc[j])
        if j != k:
            ret -= a[j] + x

    return ret


def main():
    n, m = map(int, input().split())
    *a, = map(int, input().split())
    print(solve(n, m, a))


if __name__ == '__main__':
    main()


Fixed, accepted submission:


def main():
    N, M = map(int, input().split())
    *a, = map(int, input().split())
    a.sort()

    def count(mid) -> int:
        cnt = 0  
        j = N  
        for i in range(N):
            while j > 0 and a[i] + a[j - 1] >= mid:
                j -= 1
            # j==0 or a[i]+a[j]>=mid
            # j==0
            
            
            cnt += N - j  
        return cnt

    def binary_search(*, ok: int, ng: int, is_ok: 'function') -> int:
        
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    ma = binary_search(ok=2 * 10 ** 5 + 1, ng=0, is_ok=lambda mid: count(mid) < M)

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    *acc, = accumulate(a)

    ans = 0
    j = N  
    for i in range(N):
        while j > 0 and a[i] + a[j - 1] >= ma:
            j -= 1
        ans += a[i] * (N - j) + acc[N] - acc[j]  
    ans += (ma - 1) * (M - count(ma))  

    print(ans)


if __name__ == '__main__':
    main()