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 bisect
from itertools import accumulate


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

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


def calc(x):
    _total = 0
    _num = 0
    for i in range(N):
        j = bisect.bisect_left(A, x - A[i])
        _num += N - j
        _total += S[N] - S[j]
        _total += A[i] * (N - j)
    return _total, _num


left = 0
right = 200005

while right - left > 1:
    center = (left + right) // 2
    if calc(center)[1] >= M:
        left = center
    else:
        right = center

total, num = calc(left)
ans = total
ans -= (num - M) * left
print(ans)

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

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = [0] + list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    happy += cumsum_A[-1] - cumsum_A[idx] + cnt * j
    M -= cnt

happy += M * X

print(happy)

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

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

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

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

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

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 10 ** 6

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Solution (Python):

import sys

INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            
            mid = (left+right)//2
            
            
            
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            
            if c > M:
                left = mid

            else:
                right = mid
        
        if c > M:
            s -= (c-M)*mi

        return s

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

    print(binary_search(1, A[-1]*2))
    
    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):
import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        x = (left + right) // 2

        count = N**2 - np.searchsorted(A, x-A).sum()

        if count >= M:
            left = x
        else:
            right = x

    bound = np.searchsorted(A, left-A)
    count = N**2 - bound.sum()
    diff = count - M
    ans = ((N - bound) * A * 2).sum() - diff * left

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):





from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print(ans * 2 - diff * left)


if __name__ == "__main__":
    main()

Solution (Python):





from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print(ans * 2 - diff * left)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): 
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*(10**5)+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    C=n-np.searchsorted(A,right-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    print(np.sum(A*C)+left*(m-cnt)+B[C[np.where(C>0)]-1].sum())
if __name__=='__main__':
    main()

Solution (Python):
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): 
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*10**5+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    s=np.sum(A*C)+border*(m-cnt)+B[C[np.where(C>0)]-1].sum()
    print(s)
if __name__=='__main__':
    main()

Solution (Python):
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): 
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=10**10*1
    left=-10**10-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    

    s,cnt=0,0
    for i in range(n):
        if C[i]>0:
          cnt+=C[i]
          s+=B[C[i]-1]+A[i]*C[i]
    s+=border*(m-cnt)

    print(s)
if __name__=='__main__':
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    def helper(x):
        p = len(A) - 1
        t = 0
        for a in A:
            while p >= 0 and A[p] + a < x:
                p -= 1
            t += p + 1
        return t
    l, r = 0, A[0] * 2 + 1
    while r - l > 1:
        m = (l + r) // 2
        if helper(m) > M:
            l = m
        else:
            r = m
    k = sum(A)
    p = len(A) - 1
    t = (M - helper(l)) * l
    for a in A:
        while p >= 0 and A[p] + a < l:
            k -= A[p]
            p -= 1
        t += a * (p + 1) + k
    print(t)

main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl())
ng = 10**9+1
ok = -1
def sol(x):
    cnt = 0
    for i,t in enumerate(a):
        tmp = x - t
        c = bisect.bisect_left(a,tmp)
        cnt += n-c
    return True if cnt >= m else False

while ng-ok > 1:
    mid = (ng+ok)//2
    if sol(mid):
        ok = mid
    else: ng = mid
    

res = 0
cnt = 0
revc = [0]
for i in range(n)[::-1]:
    revc.append(revc[-1] + a[i])

for i in range(n):
    j = n-bisect.bisect_left(a,ok-a[i])
    res += j*a[i] + revc[j]
    cnt += j
res -= (cnt-m) * ok
print(res)

Solution (Python):
from bisect import bisect_left
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
maxA = max(A)
cnt = [0] * (maxA * 2 + 2)
rui = [n] * (maxA * 2 + 2)

for a in A:
  cnt[a] += 1

accum = 0  
for i in range(maxA * 2 + 1):
  accum += cnt[i]
  rui[i + 1] -= accum 
  

def f(x):
  ret = 0
  for left in A:
    ret += rui[max(x - left, 0)]
  return ret
  
lo = 0
hi = maxA * 2 + 1
while hi - lo > 1:
  md = (lo + hi) // 2
  if f(md) >= m:
    lo = md
  else:
    hi = md 

    
ruiA = [0] * (n + 1)
for i in range(n):
  ruiA[i + 1] = ruiA[i] + A[i]

ans = 0
cnt = 0
for i in range(n):
  pos = bisect_left(A, lo - A[i])
  cnt += n - pos
  ans += ruiA[-1] - ruiA[pos] + A[i] * (n - pos)
if cnt == m:
  print(ans)
else: 
  rem = cnt - m
  print(ans - rem * lo)

Solution (Python):
import bisect
from itertools import accumulate
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A2 = [0]+list(accumulate(A))
def judge(mid):
    count = 0
    for i in range(N):
        border = mid - A[i]
        ind = bisect.bisect_left(A,border)
        count += N-ind
    if count < M:
        return True
    else:
        return False
mina = 0
maxa = 2*(10**5) + 1
while maxa-mina > 1:
    mid = (maxa+mina)//2
    if judge(mid):
        maxa = mid
    else:
        mina = mid
count = 0
ans = 0
for i in range(N):
    border = maxa - A[i]
    ind = bisect.bisect_left(A,border)
    count += N-ind
    ans += A[i]*(N-ind) + A2[N]-A2[ind]
if count == M:
    print(ans)
else:
    rem = M-count
    print(ans+rem*mina)

Solution (Python):
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)

Solution (Python):

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

MAX = 10**10 + 10




from bisect import bisect_left

def judge(x,key):
    
    
    num = 0
    
    for i in range(N):
        eidx = bisect_left(A,x-A[i])
        num += N-eidx
    
    if num >= key:
        return True
    else: 
        return False


def meguru(key):
    ok = -1
    ng = MAX
    
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if judge(mid,key):
            ok = mid
        else:
            ng = mid
    return ok


D = meguru(M)
ans = 0

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

num = 0

for i in range(N):
    eidx = bisect_left(A,D+0.5-A[i])
    ans += A[i] * (N-eidx)
    ans += ruisekiwa[N] - ruisekiwa[eidx]
    num += N-eidx

if num<M:
    ans += (M-num)*D

print(ans)

Solution (Python):
from bisect import bisect_left
from itertools import accumulate

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])


def is_under_M(x:int):
    cnt = 0
    for i in range(N):
        
        pos = bisect_left(A, x - A[i])
        cnt += N - pos
    return cnt < M


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



Aacum = tuple(accumulate([0] + A))

ans = 0
for i in range(N):
    
    pos = bisect_left(A, ok - A[i])
    cnt = N - pos

    ans += cnt * A[i] + (Aacum[N] - Aacum[pos])
    M -= cnt

ans += M * ng

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

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

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)

Solution (Python):
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
r=a[n-1]*2+1
l=0
while r-l>=2:
	mid=(l+r)//2
	
	
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid

ans,p,=0,0
b=[0]
for i in range(n):
	p+=a[i]
	b.append(p)
for i in range(n):
	q=bisect.bisect_left(a,r-a[i])
	ans+=b[n]-b[q]
	ans+=a[i]*(n-q)
	k-=n-q
ans+=l*k
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from itertools import accumulate

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])


def is_under_M(x:int):
    cnt = 0
    for i in range(N):
        
        pos = bisect_left(A, x - A[i])
        cnt += N - pos
    return cnt < M


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



Aacum = tuple(accumulate([0] + A))

ans = 0
for i in range(N):
    
    pos = bisect_left(A, ng - A[i])
    cnt = N - pos

    ans += cnt * A[i] + (Aacum[N] - Aacum[pos])
    M -= cnt

ans += M * ng

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
r=a[n-1]*2+1
l=0
while r-l>=2:
	mid=(l+r)//2
	
	
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid

ans,p,=0,0
b=[0]
for i in range(n):
	p+=a[i]
	b.append(p)
for i in range(n):
	q=bisect.bisect_left(a,r-a[i])
	ans+=b[n]-b[q]
	ans+=a[i]*(n-q)
	k-=n-q
ans+=l*k
print(ans)

Solution (Python):
import bisect

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


num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(1, 10**5):
  j = 10**5 - i
  num_A_or_more[j-1] += num_A_or_more[j]



def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    if idx >= 10**5:
      continue
    count += num_A_or_more[idx]
  
  return count>=M



left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2


x = left



rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Solution (Python):
import bisect


N, M = map(int, input().split())
Al = list(map(int, input().split()))
Al.sort() 
Ar = Al.copy()[::-1] 

def count_large_2(L1, L2, x):
  
  
  N1, N2 = len(L1), len(L2)
  i = j = 0
  c = 0
  while i<N1 and j<N2:
    if L1[i]+L2[j] >= x:
      c += 1
      j += 1
      if j >= N2:
        c += (N1-i-1) * N2
    else:
      i += 1
      if i>=N1:
        continue
      c += j
  return c

left = 0 
right = Al[-1]*2 + 1 
while left+1 < right:
  mid = (left + right) // 2
  if count_large_2(Al, Ar, mid) >= M:
    left = mid
  else:
    right = mid


x = left
accum_A = [Ar[0]]
for i, a in enumerate(Ar):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
surplus = 2*10**5
for ai in Ar:
  idx = bisect.bisect_left(Al, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+Al[idx])
 
 
print(ans - (count-M)*surplus)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate

from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

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

ans = 0

def count(x):  
	cnt = 0
	for y in A:  
		left = -(x-y)
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for y in A:
	left = -(l-y)
	idx = bisect(B, left)
	ans += A_acc[idx]+idx*y
	cnt += idx
ans -= (cnt-M)*l

print(ans)

Solution (Python):
N,M=map(int,input().split())
A=sorted(map(int,input().split()))
B=[0]
for a in A:
    B.append(B[-1]+a)
def f(n):
    a,b=0,0
    r=N-1
    for l in range(N):
        while r>-1 and A[l]+A[r]>=n:
            r-=1
        a+=N-1-r
        b+=A[l]*(N-1-r)+B[N]-B[r+1]
    return a,b
l,r=0,10**6
x=0
while l+1<r:
    t=(l+r)//2
    a,b=f(t)
    if a<M:
        r=t
    else:
        x=max(x,t)
        l=t
a,b=f(x)
print(b-x*(a-M))

Solution (Python):
from bisect import bisect_left
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))


ok, ng = 0, 2 * 10 ** 5 + 1
while abs(ok - ng) > 1:
    X = (ok + ng) // 2
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, X - a)
        if cnt >= M:
            ok = X
            break
    else:
        ng = X


ans = 0
cnt = 0
A_acc = [0] + list(accumulate(A[::-1]))[::-1]

for a in A:
    i = N - bisect_left(A, ok - a)
    cnt += i
    ans += a * i + A_acc[-i]


ans -= max(0, cnt - M) * ok
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))





import bisect

ok=-1
ng=(10**10)+1


def isOk(x,m):
  cnt=0
  
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok




Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  



ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))





import bisect

ok=-1
ng=(10**10)+2


def isOk(x,m):
  cnt=0
  
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok




Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  



ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007




def count_al(al, vv):
	
	
	
	rui=0
	for v in al:
		r = get_ok_index(v, al, vv)
		rui += r
	return rui

def get_ok_index(v,al,ok_value):
	
	
	
	if v+al[0] < ok_value:
		return 0
	if v + al[-1] >= ok_value:
		return len(al)
	ok=0
	ng=len(al)
	while ok + 1 < ng:
		
		m=(ok+ng)//2
		if v+al[m] >= ok_value:
			ok = m
		else:
			ng = m
		
	return ok+1
	

def main():
	n, m = IN()
	al = list(IN())
	al.sort(reverse=True)
	if m == n*n:
		ret= sum(al) * n * 2
	
	ruisekiwa=al[:]
	for i,v in enumerate(al[1:],1):
		ruisekiwa[i]=ruisekiwa[i-1]+v
	
		
	ok=al[0]*10
	ng=0
	
	while ok  > ng + 1:
		vv = (ok + ng)//2
		cc = count_al(al, vv)
		
		if cc <= m:
			ok = vv
		else:
			ng = vv
	
	
	ret=0
	for v in al:
		ok_id = get_ok_index(v, al, ok)-1
		
		if ok_id==-1:
			continue
		ret += ruisekiwa[ok_id]+v*(ok_id+1)
	
	ret += (ok - 1)*(m-count_al(al,ok))
	print(ret)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
left=0
right=(10**5)*2+5
s=ruiseki(a)

ans=0
while 1:
    mid=(left+right)//2
    cnt=0
    for i in range(n):
        tmp=bisect.bisect_left(a,mid-a[i])
        cnt+=n-tmp
    
    if cnt<m:
        right=mid
    else:
        left=mid
    
    
    if right-left<=1:
        break
for i in range(n):
    tmp=bisect.bisect(a,left-a[i])
    cnt=n-tmp
    ans+=cnt*a[i]+s[n]-s[tmp]
    m-=cnt
ans+=m*left
print(ans)

Solution (Python):
import bisect

n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
s=[0 for _ in range(n+1)]
for i in range(n):
    s[i+1]=s[i]+a[i]

def calc(x):
    tot=0
    num=0
    for i in range(n):
        j=bisect.bisect_left(a, x-a[i])
        num+=n-j
        tot+=s[n]-s[j]
        tot+=a[i]*(n-j)
    return [tot, num]

l=0
r=(10**5)*2+5
while l+1<r:
    c=(l+r)//2
    if calc(c)[1]>=m:
        l=c
    else:
        r=c
p=calc(l)
ans=p[0]
ans-=(p[1]-m)*l
print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = np.array(lr())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A, x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0
while right > left + 1:
    mid = (right+left) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, right-A)
happy = (Acum[-1]-Acum[Y]).sum() + (A * (N-Y)).sum()
happy += left * (M-shake_cnt(right))
print(happy)

Solution (Python):
from bisect import bisect_left
from itertools import accumulate

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

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

left = 0
right = max(A) * 2 + 1

while left + 1 < right:
  mid = (left + right) // 2
  tmp = 0
  for i in range(N):
    bi = bisect_left(A, mid - A[i])
    tmp += N - bi
  if tmp <= M:
    right = mid
  else:
    left = mid

cnt = 0
answer = 0
for i in range(N):
  bi = bisect_left(A, right - A[i])
  cnt += N - bi
  answer += Acum[N] - Acum[bi] + A[i] * (N - bi)

print(answer + (M - cnt) * left)

Solution (Python):
from bisect import bisect_left
from itertools import accumulate

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

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

left = 0
right = 10 ** 10 + 1

while left + 1 < right:
  mid = (left + right) // 2
  tmp = 0
  for i in range(N):
    bi = bisect_left(A, mid - A[i])
    tmp += N - bi
  if tmp <= M:
    right = mid
  else:
    left = mid

cnt = 0
answer = 0
for i in range(N):
  bi = bisect_left(A, right - A[i])
  cnt += N - bi
  answer += Acum[N] - Acum[bi] + A[i] * (N - bi)

print(answer + (M - cnt) * left)

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

scale = 20
h = 0
gauge = 2 ** scale
import bisect
while gauge > 0:
  h += gauge
  tmp = 0
  for i in range(n):
    b = bisect.bisect_left(a,h-a[i])
    tmp += n - b
  if tmp >= m:
    pass
  else:
    h -= gauge
  gauge //= 2


ans = 0
num = 0
cum = [0]
for i in range(n):
  cum.append(cum[-1]+a[-1-i])
cum.reverse()
for i in range(n):
  b = bisect.bisect_left(a,h-a[i])
  ans += cum[b]
  ans += a[i] * (n-b)
  num += n - b
  
ans -= (num-m) * h

print(ans)

Solution (Python):
import numpy as np
N, M = list(map(int, input().split()))
A = [int(_) for _ in input().split()]
x = np.zeros(2 ** 18)
for a in A:
  x[a] += 1

y = np.fft.fft(x)

for k in range(len(y)):
  y[k] *= y[k]

x = np.fft.ifft(y).real

happiness = 0
for i in reversed(range(0, len(x))):
  happiness += i * min(int(x[i] + 0.5), M)
  M -= int(x[i] + 0.5)
  if M <= 0:
    break

print(happiness)

Solution (Python):

import sys
input = sys.stdin.readline
import cmath
pi = cmath.pi
exp = cmath.exp

def fft(a, inverse=False):
    n = len(a)
    h = n.bit_length() - 1

    
    for i in range(n):
        j = 0
        for k in range(h):
            j |= (i >> k & 1) << (h - 1 - k)
        if i < j:
            a[i], a[j] = a[j], a[i]

    
    if inverse:
        sign = 1.0
    else:
        sign = -1.0
    b = 1
    while b < n:
        for j in range(b):
            w = exp(sign * 2.0j * pi / (2.0 * b) * j)
            for k in range(0, n, b*2):
                s = a[j + k]
                t = a[j + k + b] * w
                a[j + k] = s + t
                a[j + k + b] = s - t
        b *= 2

    if inverse:
        for i in range(n):
            a[i] /= n

    return a

def ifft(a):
    return fft(a, inverse=True)

def convolve(f, g):
    n = 2**((len(f) + len(g) - 1).bit_length())
    f += [0] * (n - len(f))
    g += [0] * (n - len(g))
    F = fft(f)
    G = fft(g)
    FG = [Fi * Gi for Fi, Gi in zip(F, G)]
    fg = [int(item.real + 0.5) for item in ifft(FG)]
    return fg

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [int(item) for item in input().split()]
    max_a = max(a)
    freq = [0] * (max_a + 1)
    for item in a:
        freq[item] += 1
    f = freq[:]; g = freq[:]
    fg = convolve(f, g)
    total = sum(a) * n * 2
    cnt = n * n - m
    for i, item in enumerate(fg):
        use = min(cnt, item)
        total -= i * use
        cnt -= use
        if cnt == 0:
            break
    print(total)