Problem:
 Score : 500 points    Problem Statement 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?      Constraints  1 \leq N \leq 10^5  1 \leq M \leq N^2  1 \leq A_i \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_N       Output Print the maximum possible happiness after M handshakes.        Sample Input 1 5 3
10 14 19 34 33      Sample Output 1 202  Let us say that Takahashi performs the following handshakes:   In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4 .  In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5 .  In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4 .   Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202 .  We cannot achieve the happiness of 203 or greater, so the answer is 202 .       Sample Input 2 9 14
1 3 5 110 24 21 34 5 3      Sample Output 2 1837       Sample Input 3 9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076      Sample Output 3 8128170

Solution (Python):
import sys
from collections import defaultdict
import bisect
import itertools
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    A = list(geta(int))
    A.sort()

    def c(x):
        """
        @return  
        """
        ret = 0
        for a in A:
            ret += bisect.bisect_left(A, x - a)
        return N * N - ret

    left, right = 0, 2 * A[-1] + 1

    while left + 1 < right:
        middle = (left + right) // 2
        if c(middle) >= M:
            left = middle
        else:
            right = middle

    ans = 0
    Acum = list(itertools.accumulate(A[::-1]))[::-1]
    for a in A:
        idx = bisect.bisect_left(A, right - a)
        if idx < N:
            ans += Acum[idx] + a * (N - idx)
    ans += left * (M - c(right))

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]

def cnt(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += bisect.bisect_left(A,x - a)
    return res

def ans(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += a*bisect.bisect_left(A,x-a) + S[bisect.bisect_left(A,x-a)]
    return res

top = A[-1]*2+1
bottom = 0

while top - bottom > 1:
    mid = (top + bottom)//2
    if n*n - cnt(mid,A,S) > m:
        bottom = mid
    else:
        top = mid

print(S[-1]*2*n - ans(top,A,S) + bottom*(m - (n*n - cnt(top,A,S))))

Solution (Python):

import sys
input = sys.stdin.readline

def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  
  
  
  l,r=0,a[-1]*2+1
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    
    if cnt>=m:
      l=x
    else:
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  print(ans+(m-cnt)*x)

if __name__=='__main__':
  
  
  main()

Solution (Python):
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ruiseki = list(accumulate(A[::-1]))

def syakutori(mid):
    x = 0
    cnt = 0
    ans = 0
    for i in range(N)[::-1]: 
        while x < N:
            if A[i] + A[x] >= mid:
                cnt += N - x
                if N - x >= 1:
                    ans += A[i] * (N - x) + ruiseki[N - x - 1]
                break
            else:
                x += 1

    return cnt, ans


ok = 0
ng = 10 ** 15
while ok + 1 < ng:
    mid = (ok + ng) // 2
    cnt, ans = syakutori(mid)
    if cnt >= M:
        ok = mid
    else:
        ng = mid


print(ans + ok * (M - cnt))

Solution (Python):
import sys
import  math
import fractions
from collections import defaultdict
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
A.sort()
S=[0]
S[0]=A[0]

for i in range(1,N):
    S.append(S[i-1]+A[i])

def clc_shake(x):
    tot=0
    for i in range(N):
        th=x-A[i]
        inds=bisect.bisect_left(A,th)
        tot+=(N-inds)
    return tot

l=0
r=2*(10**6)
c=0

while (l+1<r):
    c=(l+r)//2
    if(clc_shake(c)<M):
        r=c
    else:
        l=c


ans=0
for i in range(N):
        th=r-A[i]
        inds=bisect.bisect_left(A,th)
        if(inds!=0):
            ans+=((N-inds)*A[i]+(S[N-1]-S[inds-1]))
        else:
            ans+=((N-inds)*A[i]+(S[N-1]))


M2=M-clc_shake(r)
ans+=M2*(l)
print(ans)

Solution (Python):


import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, sums):
    ss = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ss += sums[n] - sums[idx]
        ss += (n - idx) * a
    
    return ss

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = max(A) * 2 + 1
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    cnt = _count(A, N, l)
    ret = _sum(A, N, l, sums)
    ret -= (cnt - M) * l
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print(i, j)
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print(j, i)
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, A)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

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

A.sort(reverse = True)


ok = -1
ng = 10 ** 11
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    left, right = 0, N - 1
    cnt = 0
    while left <= N - 1 and right >= 0:
        if A[left] + A[right] >= mid:
            cnt += right + 1
            left += 1
        else:
            if right:
                right -= 1
            else:
                left += 1
    if cnt >= M:
        ok = mid
    else:
        ng = mid


Acum = [0] + list(accumulate(A))


left, right = 0, N - 1
cnt = 0
answer = 0
while left <= N - 1 and right >= 0:
    if A[left] + A[right] >= ok:
        cnt += right + 1
        answer += (right + 1) * A[left] + Acum[right + 1]
        left += 1
    else:
        if right:
            right -= 1
        else:
            left += 1
        
answer -= (cnt - M) * ok
print(answer)

Solution (Python):
from bisect import bisect_left

N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
l = 0
r = 2*10**5+5


while l+1 < r:
    mid = (l+r) // 2
    
    m = 0
    for a in A:
        idx = bisect_left(A, mid-a)
        m += N-idx
        
    if m >= M: l = mid
    else: r = mid

s = [0] * (N+1)
for i in range(N):
    s[i+1] = s[i] + A[i]
    
ans = 0
m = 0
for a in A:
    idx = bisect_left(A, l-a)
    m += N-idx
    
    ans += s[N]-s[idx]
    ans += a*(N-idx)
    
ans -= (m-M)*l

print(ans)

Solution (Python):
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

aa = [0]*(10**5+1)
aa_sum = [0]*(10**5+1)

for x in a:
    aa[x] += 1
    aa_sum[x] += x

for i in range(10**5)[::-1]:
    aa[i] = aa[i] + aa[i+1]
    aa_sum[i] = aa_sum[i] + aa_sum[i+1]


def count(x):
    cnt = 0
    sm = 0
    for i in range(n):
        if x-a[i] < 0:
            cnt += n
            sm += aa_sum[0]+n*a[i]
        elif x-a[i] > 10**5:
            continue
        else:
            cnt += aa[x-a[i]]
            sm += aa_sum[x-a[i]]+aa[x-a[i]]*a[i]

    return cnt, sm


bottom = 0
top = 10**6

while top - bottom > 1:
    mid = (top+bottom) // 2
    cnt, sm = count(mid)
    if cnt < m:
        top = mid
    else:
        bottom = mid

cnt, sm = count(bottom)
ans = sm - (cnt-m)*bottom

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    b = sorted(a)
    c = [0] + sorted(b)
    c = list(accumulate(c))
    a.sort(reverse=True)
    
    
    def check(mid):
        total = 0
        for i in a:
            total += n - bisect_left(b, mid-i)
            if total >= m:
                return True
        return False

    l = 0
    r = 2*(10**5)+10
    
    while r - l > 1:
        mid = (l+r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    res = 0
    for i in a:
        d = bisect_left(b, r-i)
        if d == n:
            continue
        res += i * (n-d) + c[-1] - c[d]
        m -= n - d

    print(res + l*m)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N,M,*A = map(int, open(0).read().split())
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)

Solution (Python):
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open(0).read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Solution (Python):
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open(0).read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**9
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    cnt = 0
    
    for Ai in A:
        cnt += N-bisect_left(A, x-Ai+1)
    
    return cnt<M

def binary_search():
    l, r = 0, 2*max(A)
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0]*(N+1)

for i in range(N):
    acc[i+1] = acc[i]+A[i]
    
cnt = 0
ans = 0

for Ai in A:
    j = bisect_left(A, border-Ai+1)
    cnt += N-j
    ans += (N-j)*Ai+acc[N]-acc[j]

ans += (M-cnt)*border
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n, m = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()

    def count(x): 
        res = 0
        for a in A:
            idx = bisect_left(A, x - a)
            res += n - idx
        return res

    left = 0
    right = 200001
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid) < m:
            right = mid
        else:
            left = mid

    x = right
    res = 0
    for a in A:
        idx = bisect_left(A, x - a)
        res += 2 * a * (n - idx)
    res += (x - 1) * (m - count(x))
    print(res)
resolve()

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(x):
  c = 0
  for y in a:
    ok = N
    ng = -1
    while ok - ng > 1:
      m = (ok + ng) // 2
      if a[m] + y >= x: ok = m
      else: ng = m
    c += N - ok
  return c >= M

ok = 0
ng = 10 ** 6
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m

l = ok + 1
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

res = 0
c = 0
for x in a:
  ok = N
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if a[m] + x >= l: ok = m
    else: ng = m
  c += N - ok
  res += cs[-1] - cs[ok] + x * (N - ok)

print(res + (l - 1) * (M - c))

Solution (Python):
import bisect

if __name__ == '__main__':
    def check(mid):
        count = 0
        for i in range(n):
            position = bisect.bisect_left(a, (mid - a[i]))
            count += (n - position)
        return count < m


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

    

    ng = 0
    ok = 10 ** 5 * (n + 1)

    while 1 < abs(ok - ng):
        
        mid = (ok + ng) // 2
        c = check(mid)
        
        if c:
            ok = mid
        
        else:
            ng = mid

    

    
    
    

    ans = 0
    sum_array = [0] * (n + 1)
    
    
    

    for i in range(n):
        sum_array[i + 1] = sum_array[i] + a[i]
    for i in range(n):
        position = bisect.bisect_right(a, ng - a[i])
        ans += (n - position) * a[i] + sum_array[n] - sum_array[position]
        m -= (n - position)

    ans += ng * m
    print(ans)

Solution (Python):
from copy import copy

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = copy(a)
b.reverse()

def count_more_x(x : int):
    j = 0
    ret = 0
    for i in range(len(b)):
        while j < len(a) and b[i]+a[j] < x:
            j += 1
        ret += j
    return n*n-ret

def sum_more_x(x : int):
    j = 0
    ret = 0
    for i in range(len(b)):
        while j < len(a) and b[i]+a[j] < x:
            j += 1
        ret += b[i]*(n-j)+c[j]
    return ret

lower = 0
upper = 1000000
while upper-lower > 1:
    middle = (upper+lower)//2
    if count_more_x(middle) < m:
        upper = middle
    else:
        lower = middle

left = lower

lower = 0
upper = 1000000
while upper-lower > 1:
    middle = (upper+lower)//2
    if count_more_x(middle) >= m:
        lower = middle
    else:
        upper = middle

right = upper



c = copy(a)
value = 0
for i in range(len(c)-1, -1, -1):
    value = value + c[i]
    c[i] = value
c.append(0)
ans = sum_more_x(right) + left*(m-count_more_x(right))
print(ans)

Solution (Python):
from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)

Solution (Python):
from bisect import bisect_right as br
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
b=[0]
for i in a:b.append(b[-1]+i)
ng=2*10**5+7
ok=-1
while ok+1!=ng:
  mid=(ng+ok)//2
  co=0
  for i in a:co+=br(a,-(mid+i))
  if co<m:ng=mid
  else:ok=mid
ans=0
co=0
for i in a:
  ind=br(a,-(ok+i)-1)
  co+=ind
  ans+=-b[ind]-i*ind
ans+=(m-co)*ok
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)


l = [n for i in range(a[0]+1)]
for i in range(2, n+1):
    for j in range(a[-i], a[-i+1], -1):
        l[j] = n - i + 1



start = 2 * a[-1]
stop = 2 * a[0]
while start < stop:
    i = (start + stop + 1) // 2
    num = 0
    for j in a:
        if i - j < 0:
            num += n
        elif i - j <= a[0]:
            num += l[i - j]
        else:
            break

    if num >= m:
        start = i
    else:
        stop = i - 1

num = 0
for i in a:
    if start - i < 0:
        num += n
    elif 0 <= start - i <= a[0]:
        num += l[start - i]
    else:
        break


ans = 0
for i in a:
    if start - i < 0:
        ans += 2 * i * n
    elif start - i <= a[0]:
        ans += 2 * i * l[start - i]
    else:
        break
ans -= (num - m) * start
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)


l = [n for i in range(a[0]+1)]
for i in range(2, n+1):
    for j in range(a[-i], a[-i+1], -1):
        l[j] = n - i + 1



start = 2 * a[-1]
stop = 2 * a[0]
while start < stop:
    i = (start + stop + 1) // 2
    num = 0
    for j in a:
        if i - j < 0:
            num += n
        elif i - j <= a[0]:
            num += l[i - j]
        else:
            break

    if num >= m:
        start = i
    else:
        stop = i - 1

num = 0
for i in a:
    if start - i < 0:
        num += n
    elif 0 <= start - i <= a[0]:
        num += l[start - i]
    else:
        break


ans = 0
for i in a:
    if start - i < 0:
        ans += 2 * i * n
    elif start - i <= a[0]:
        ans += 2 * i * l[start - i]
    else:
        break
ans -= (num - m) * start
print(ans)

Solution (Python):
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            if arg-i <= 10**5:
                x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    if num <= 10**5:
        ans += 2*i*cs[num]
        count += cs[num]
ans -= (count-m)*h
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import bisect

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    
    a.sort()
    cum = [0]
    for num in a:
        cum.append(cum[-1]+num)
    
    def power(x):
        count = 0
        for num in a:
            rest = x-num
            index = bisect.bisect_left(a,rest)
            count += N-index
        if count >= M:
            return True
        else:
            return False
    
    l,r = -1,10**10
    while r-l > 1:
        mid = (r+l)//2
        if power(mid):
            l = mid
        else:
            r = mid
            
    border = r
    
    count,ans = 0,0
    for num in a:
        rest = border-num
        index = bisect.bisect_left(a,rest)
        ans += (N-index)*num
        ans += cum[N]-cum[index]
        count += N-index
        
    print(ans+(M-count)*l)
        

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=map(int,input().split())
A=sorted(map(int,input().split()))
left,right=-1,(10**5)*2+1
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)+(r[N]-r[b])
    cnt+=N-b
print(ans-D*(cnt-M))

Solution (Python):


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
            
            
            
            
            cnt += N - j  
        return cnt

    def binary_search(*, ok: int, ng: int, is_ok: 'function') -> int:
        """あるペア和以上のみ採用する場合に
        M回以上握手できないようなペア和の上限"""
        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()

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left
from itertools import accumulate

def func(A, N, M, x):
    count = 0
    for Ai in A:
        idx = bisect_left(A, x - Ai)
        count += N - idx
    if count >= M:
        return True
    else:
        return False

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    A_rev = list(reversed(A))
    B = [0] + list(accumulate(A_rev))
 
    min_ = 0
    max_ = 2 * 10 ** 5 + 1
    while max_ - min_ > 1:
        mid = (min_ + max_) // 2
        if func(A, N, M, mid):
            min_ = mid
        else:
            max_ = mid
    
    ans = 0
    count = 0
    for Ai in A_rev:
        idx = bisect_left(A, min_-Ai)
        ans += Ai * (N - idx) + B[N-idx]
        count += N - idx
    print(ans-(count-M)*min_)

if __name__ == '__main__':
    main()

Solution (Python):
import bisect


def solve(mid):
    cnt = 0
    l = n
    r = n
    for i in range(n):
        while True:
            if l == 0:
                break
            if a[l - 1] < mid - a[i]:
                break
            l -= 1
        cnt += (r - l)
    return cnt >= m
    

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

ok = 0
ng = 2 * 10 ** 5 + 10
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + a[i]

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.bisect_left(a, ok - a[i])
    cnt += (r - l)
    ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)

Solution (Python):
import bisect


def solve(mid):
    cnt = 0
    l = n
    r = n
    for i in range(n):
        while True:
            if l == 0:
                break
            if a[l - 1] < mid - a[i]:
                break
            l -= 1
        cnt += (r - l)
    return cnt >= m
    

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

ok = 0
ng = 10 ** 18
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + a[i]

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.bisect_left(a, ok - a[i])
    cnt += (r - l)
    ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)

Solution (Python):
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r
from itertools import accumulate

n, m, *a = map(int, sys.stdin.read().split())
a.sort()

def count(border):
  res = 0
  for x in a:
    b = border - x
    res += n - bi_l(a, b)
  return res

def main():
  lo, hi = 1, a[-1] * 2 + 1
  while lo + 1 < hi:
    border = (lo + hi) // 2
    if count(border) >= m:
      lo = border
    else:
      hi = border
  
  s = a.copy() + [0]
  *s, = accumulate(s[::-1])
  tot = 0
  for x in a:
    b = lo - x
    c = n - bi_l(a, b)
    tot += x * c + s[c]
  
  tot -= lo * (count(lo) - m)
  print(tot)

if __name__ == '__main__':
  main()

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import bisect
def count(k):
    
    cnt=0
    for i in range(n):
        cnt+=n-bisect.bisect_left(a,k-a[i])
    return cnt

l=0
r=2*10**5+10

while r-l>1:
    med=(r+l)//2
    if count(med)<m:
        r=med
    elif count(med)>=m:
        l=med


ans=0

dp=[0 for i in range(n+1)]

for i in range(1,n+1):
    dp[i]=dp[i-1]+a[-i]

for i in range(n):
    x=a[i]
    index=n-bisect.bisect_left(a,l-x)
    ans+=dp[index]+x*index
    
print(ans-l*(count(l)-m))

Solution (Python):
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi

    return n**2-num

mi = a[0]*2-1
ma = a[-1]*2+1
kotae=ma
while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m
    if which:
        ma=now
        kotae=now
    else:
        mi=now+1
kotae-=1

suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]
    
ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,kotae-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*kotae)

Solution (Python):
def main():
    from bisect import bisect_right

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

    def calc(x):
        tmp = 0
        for a in A:
            tmp += N - bisect_right(A, x - a - 0.5)
        return tmp

    l = 0
    r = 3 * 10 ** 5
    while r - l > 1:
        mid = (l + r) // 2
        if calc(mid) >= M:
            l = mid
        else:
            r = mid

    B = [0] * (N + 1)
    for i in range(N):
        B[i + 1] = B[i] + A[i]

    ans = 0
    for a in A:
        tmp = bisect_right(A, r - a - 0.5)
        M -= (N - tmp)
        ans += a * (N - tmp) + (B[-1] - B[tmp])

    ans += M * l
    print (ans)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

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

def calc(m): 
    count = 0 
    for a in A:
        b = m - a 
        count += N - bisect_right(A, b - 0.5)
    return count

l = 0 
r = 3 * 10 ** 5

while r - l > 1:
    mid = (l + r) // 2
    if calc(mid) >= M: 
        l = mid
    else:
        r = mid

B = [0] * (N + 1)
for i in range(N):
    B[i + 1] = B[i] + A[i]


flag = False
for i in range(mid + 3, -1, -1):
    if calc(i) < M:
        flag = False
    else: 
        break

i += 1 
ans = 0
for a in A:
    b = i - a
    tmp = bisect_right(A, b - 0.5)
    M -= (N - tmp) 
    ans += a * (N - tmp) + (B[-1] - B[tmp])

ans += M * (i - 1)
print (ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    import bisect

    ok = 0
    ng = 2 * max(a) + 1

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        count = 0
        i = 0
        for elem in a:
            minlim = mid - elem
            count += (n - bisect.bisect_left(a, minlim))

        if count >= m:
            ok = mid
        else:
            ng = mid

    from itertools import accumulate

    a_cum = list(accumulate(a[::-1]))
    a_cum = a_cum[::-1] + [0]
    ans = 0
    j = n
    cnt_over = 0

    for elem in a:
        minlim = ok - elem + 1
        idx = bisect.bisect_left(a, minlim)
        ans += a_cum[idx]
        ans += elem * (n - idx)
        cnt_over += (n - idx)

    ans += ok * (m - cnt_over)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    a_desc = a[::-1]

    ok = 0
    ng = 2 * max(a) + 1

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        count = 0
        i = 0
        for elem in a:
            while i < n:
                if elem + a_desc[i] >= mid:
                    i += 1
                else:
                    break
            count += i
        if count >= m:
            ok = mid
        else:
            ng = mid

    from itertools import accumulate

    a_cum = list(accumulate(a_desc))
    a_cum = a_cum[::-1] + [0]
    ans = 0
    j = n
    cnt_over = 0

    for elem in a:
        while j > 0:
            if elem + a[j - 1] > ok:
                j -= 1
            else:
                break
        cnt_over += (n - j)
        ans += a_cum[j]
        ans += elem * (n - j)

    ans += ok * (m-cnt_over)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, m = map(int, readline().split())
a = np.array(read().split(), np.int64)
a.sort()


def check(mid):
    mid = np.searchsorted(a, mid - a)
    return n * n - mid.sum() >= m


left = 0
right = 10 ** 6
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        right = mid

mid = np.searchsorted(a, right - a)
cumsum = np.zeros(n + 1, np.int64)
cumsum[1:] = np.cumsum(a)
ans = (cumsum[-1] - cumsum[mid]).sum() + (a * (n - mid)).sum() + (m - n * n + mid.sum()) * left
print(ans)