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 itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*3
lb = -1
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = lb
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)


if tmp > m:
    ans -= (tmp-m)*target
print(ans)

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

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
A_rev = list(reversed(A))
B = [0] + list(accumulate(A_rev))

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

min_ = 0
max_ = 2 * 10 ** 5 + 1
while max_ - min_ > 1:
    mid = (min_ + max_) // 2
    if func(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_)

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


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = [0] + list(accumulate(A))

def check(X):
    cnt = 0
    for i in range(N):
        cnt += N - bisect_left(A, X - A[i])
    return cnt >= M


def main():

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

    ans = 0
    cnt = 0
    for i in range(N):
        tmp = bisect_left(A, ok - A[i])
        cnt += N - tmp
        ans += B[N] - B[tmp]
        ans += A[i] * (N - tmp)
    ans -= ok * (cnt - M)
    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))
    an = aa[n]

    ok = 0
    ng = 10**10
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if sum([n-bl(a, mid-a[i]) for i in range(n)]) >= m:
            ok = mid
        else:
            ng = mid

    c = -m+sum([n-bl(a, ok-a[i]) for i in range(n)])
    ans = -c*ok
    for i in range(n):
        d = bl(a, ok-a[i])
        ans += an-aa[d]+(n-d)*a[i]
    print(ans)


main()

Solution (Python):
N,M = map(int,input().split())
*A, = map(int,input().split())

A.sort(reverse=True)

def count(i,B):
    B = B - A[i]
    l = -1
    r = N
    while l+1<r:
        j = (l+r)//2
        if A[j] >= B:
            l = j
        else:
            r = j
    return r

l = 0
r = 10**5*3
while l+1<r:
    i = (l+r)//2
    S = 0
    for j in range(N):
        S += count(j,i)
    if S==M:
        r = i
        break
    elif S>M:
        l = i
    else:
        r = i

ans = 0
tmp = 0
SA = [0]*(N+1)
for j in range(N):
    SA[j+1] = SA[j] + A[j]
for j in range(N):
    c = count(j,r)
    ans += A[j]*c + SA[c]
    tmp += c
if M>tmp:
    n = 0
    for j in range(N):
        c = count(j,r)
        if c==N: continue
        n = max(n,A[j] + A[c])
    ans += n*(M-tmp)
print(ans)

Solution (Python):
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    aa = [0]+list(ac(a))
    an = aa[n]

    ok = 0
    ng = 10**10
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        q = 0
        for i in range(n):
            q += n-bl(a, mid-a[i])
        if q >= m:
            ok = mid
        else:
            ng = mid

    b = ok
    c = -m
    for i in range(n):
        c += n-bl(a, b-a[i])
    ans = -c*b
    for i in range(n):
        d = bl(a, b-a[i])
        ans += an-aa[d]+(n-d)*a[i]
    print(ans)


main()

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


def main():
    from itertools import accumulate

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

    acc = [0]
    for x in accumulate(A):
        acc.append(x)

    def count(h):
        ret = 0

        j = N
        for i in range(N):
            while j - 1 >= 0 and A[i] + A[j - 1] >= h:
                j -= 1
            ret += N - j
            

        return ret

    x = binary_search(ok=A[-1] * 2 + 1, ng=0, is_ok=lambda x: count(x) < M)
    

    s = 0
    j = N
    for i in range(N):
        while j - 1 >= 0 and A[i] + A[j - 1] >= x:
            j -= 1
        s += A[i] * (N - j) + acc[N] - acc[j]
    s += (M - count(x)) * (x - 1)

    print(s)


if __name__ == '__main__':
    main()

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

n, m = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
c = 0
s = 0


def f(x):
    global c, s
    c = 0
    s = 0
    for i in range(n):
        left = bisect_left(a, x - a[i])
        c += n - left
        s += cs[n] - cs[left] + (n - left) * a[i]
    return c


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

print(s - (c - m) * ok)

Solution (Python):
from bisect import bisect_left
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] = a[i] + b[i]
    ok = 0; ng = 2 * 10**5 + 5
    while ok+1 < ng:
        mid = (ok + 1 + ng) // 2
        buf = 0
        for i in range(n):
            p = mid - a[i]
            buf += n - bisect_left(a, p)
        if buf >= m:
            ok = mid
        else:
            ng = mid
    ans = 0
    num = 0
    tot = 0
    for i in range(n):
        p = ok - a[i]
        index = bisect_left(a, p)
        num += n - index
        tot += b[n] - b[index]
        tot += a[i] * (n-index)
    ans = tot - (num - m) * ok
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[[0]*n for k in range(2)]
ii=0
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[ii][i]=c
    d=d+c
  if d<m:
    ok=mid
    ii=(ii+1)%2
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  x=B[(ii+1)%2][i]
  ans=ans+A[i]*x+D[x]
ans=ans+(m-sum(B[(ii+1)%2]))*ok
print(ans)

Solution (Python):

import numpy as np
N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = np.fft.rfft(x, fft_size)
conv = np.fft.irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
    h = happy.pop()
    num = cnt.pop()
    num = min(M, num)

    M -= num
    ans += num * h

print(ans)

Solution (Python):
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**6

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))

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

def main():
    def check(x):
        count = 0
        for a in aaa:
            if x <= a:
                count += n
            else:
                count += n - bisect_left(aaa, x - a)
        return count >= m
    
    
    n, m = map(int, input().split())
    aaa = list(map(int, input().split()))
    aaa.sort()
    acc = [0] + list(accumulate(aaa))
    sum_a = acc[-1]
    
    l, r = 0, 200001
    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    
    
    ans = 0
    count = 0
    for a in aaa:
        if l <= a:
            ans += sum_a + a * n
            count += n
        else:
            omit = bisect(aaa, l - a)
            if omit < n:
                ans += sum_a - acc[omit] + a * (n - omit)
                count += n - omit
    ans += l * (m - count)
    print(ans)
    
if __name__ == '__main__':
    main()

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
lb = 0
ub = 2*10**5+1
while ub - lb > 1:
    m = (lb + ub) // 2
    cnt = 0
    s, t = 0, N-1
    while t >= 0:
        while s < N and A[s] + A[t] >= m:
            s += 1
        cnt += s
        t -= 1

    if cnt >= M:
        lb = m
    else:
        ub = m

accum = list(accumulate([0] + A))
ans = 0
cnt = 0
s, t = 0, N-1
while t >= 0:
    while s < N and A[s] + A[t] >= lb:
        s += 1
    ans += accum[s] + s * A[t]
    cnt += s
    t -= 1
print(ans - (cnt-M) * lb)

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

import numpy as np

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

N, M = map(int, input().split())
A = np.array(input().split(),np.int64)
A.sort()

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



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

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


def f(x):
    
    cnt = 0
    for ai in a:
        cnt += bisect_left(a, x-ai)
    
    return n * n - cnt < m


left = a[0] * 2
right = a[-1] * 2
while right - left > 1:
    mid = (right + left) // 2
    if f(mid):
        right = mid
    else:
        left = mid
ans = 0
cumsum = [0] + list(accumulate(a))
j = 0
for ai in a:
    i = bisect_left(a, left-ai)
    j += n - i
    ans += ai * (n - i) + cumsum[-1] - cumsum[i]
ans += (m - j) * left
print(ans)

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

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


def f(x):
    
    cnt = 0
    for ai in a:
        cnt += bisect_left(a, x-ai)
    
    return n * n - cnt < m


left = a[0] * 2
right = a[-1] * 2
while right - left > 1:
    mid = (right + left) // 2
    if f(mid):
        right = mid
    else:
        left = mid
ans = 0
cumsum = [0] + list(accumulate(a))
j = 0
for ai in a:
    i = bisect_left(a, left-ai)
    j += n - i
    ans += ai * (n - i) + cumsum[-1] - cumsum[i]
ans += (m - j) * left
print(ans)

Solution (Python):



from heapq import *






N,M=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
"""
lst=[]
for i in range(N):
    for m in range(N):
        lst.append(A[i]+A[m])
lst=sorted(lst,reverse=True)

print(lst)
"""
ng=-1
ok=max(A)*2+1
while ok>ng+1:
    mid=(ok+ng)//2
    K=0
    idx=0
    for i in range(N-1,-1,-1):
        X=mid-A[i]
        while idx<N and A[idx]>=X:
            idx+=1
        K+=idx
    if K>M:
        ng=mid
    else:
        ok=mid
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=ng-A[i]
    while idx<N and A[idx]>=X:
        idx+=1
    lst[i]=idx*2
value=0
for a,i in zip(A,lst):
    value+=a*i
value-=ng*(sum(lst)//2-M)
print(value)

Solution (Python):
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
A=[0]
for i in range(n):
  A.append(a[i]+A[-1])
l=0;r=10**10+1
while r-l>1:
  x=(l+r)//2
  ct=0
  for i in range(n):
    ct+=n-bisect.bisect_left(a,x-a[i])
  if ct<m:
    r=x
  else:
    l=x
ans=0
ct2=0
for i in range(n):
  y=bisect.bisect_left(a,l-a[i])
  ans+=A[n]-A[y]
  ans+=a[i]*(n-y)
  ct2+=n-y
print(ans-l*(ct2-m))

Solution (Python):
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
A=[0]
for i in range(n):
  A.append(a[i]+A[-1])
l=0;r=10**10+1
while abs(l-r)>1:
  x=(l+r)//2
  ct=0
  for i in range(n):
    ct+=n-bisect.bisect_left(a,x-a[i])
  if ct<m:
    r=x
  else:
    l=x
ans=0
ct2=0
for i in range(n):
  y=bisect.bisect_left(a,l-a[i])
  ans+=A[n]-A[y]
  ans+=a[i]*(n-y)
  ct2+=n-y
print(ans-l*(ct2-m))

Solution (Python):




import bisect
n,m = map(int, input().split())
a = list(map(int, input().split( )))
a.sort()
a2 = [a[i]*2 for i in range(n)]

mn = -1
mx = (a[-1]+1)*2
md = (mx+mn)//2
while mx-mn>1:
    md = (mx+mn)//2
    cnt = 0
    for i in range(n):
        tmp = md-a[i]
        idx = bisect.bisect_left(a, tmp)
        cnt += n-idx

    if cnt >= m:
        mn = md
    else:
        mx = md
ans = 0

acc = []
sm = 0
for i in range(n):
    sm += a[i]
    acc.append(sm)
acc.append(0)

for i in range(n-1,-1,-1):
    idx = bisect.bisect_left(a,mx-a[i])
    tmp2 = n-idx
    if m>=tmp2:
        ans += a[i] * tmp2
        ans += (acc[n-1] - acc[idx-1])
        m-=tmp2
    else:
        ans += a[i]*m
        ans += acc[n-1]-acc[n-1-m]
        break
if m:
    ans += mn*m

print(ans)

Solution (Python):
def e_handshake():
    import numpy as np
    N, M = [int(i) for i in input().split()]
    A = np.array(input().split(), np.int64)
    A.sort()

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

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

    
    X = np.searchsorted(A, right - A)  
    Acum = np.zeros(N + 1, np.int64)  
    Acum[1:] = np.cumsum(A)
    happiness = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

    
    shake = N * N - X.sum()
    happiness += (M - shake) * left
    return happiness

print(e_handshake())

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

def condition(num):
    count=0
    s=N-1
    t=0
    while N-1>=t and s>=0:
        if num>A[s]+A[t]:
            t+=1
        else:
            count+=N-t
            s-=1
    return count>=M

subans=0
start=1
end=2*A[N-1]
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    subans=end
else:
    subans=start

data=[0]*N
count=0
s=N-1
t=0
while N-1>=t and s>=0:
    if subans>A[s]+A[t]:
        t+=1
    else:
        count+=N-t
        data[s]=2*(N-t)
        s-=1

ans=sum(data[i]*A[i] for i in range(0,N))
if count>M:
    ans-=(count-M)*subans
print(ans)

Solution (Python):
import sys

input=sys.stdin.readline

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

def condition(num):
    count=0
    s=N-1
    t=0
    while N-1>=t and s>=0:
        if num>A[s]+A[t]:
            t+=1
        else:
            count+=N-t
            s-=1
    return count>=M

subans=0
start=1
end=2*A[N-1]
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    subans=end
else:
    subans=start

data=[0]*N
count=0
s=N-1
t=0
while N-1>=t and s>=0:
    if subans>A[s]+A[t]:
        t+=1
    else:
        count+=N-t
        data[s]=2*(N-t)
        s-=1

ans=sum(data[i]*A[i] for i in range(0,N))
if count>M:
    ans-=(count-M)*subans
print(ans)

Solution (Python):
from bisect import bisect_left

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

A.sort()

l=1
r=200000+1

def chk(x):
    c=0
    for la in A:
        y=bisect_left(A,x-la)
        c+=N-y
    if c>=M:
        return True
    else:
        return False



while l+1<r:
    mid=(l+r)//2
    if chk(mid):
        l=mid
    else:
        r=mid

AN=l

S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] > AN - la:
            rr = mi
        else:
            ll = mi
    c+=N-rr
    ans1=ans1+la*(N-rr)+S[N]-S[rr]

ans=ans1+(M-c)*AN
print(ans)

Solution (Python):
from bisect import bisect_left

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

A.sort()

l=1
r=200000+1

def chk(x):
    c=0
    for la in A:
        y=bisect_left(A,x-la)
        c+=N-y
    if c>=M:
        return True
    else:
        return False



while l+1<r:
    mid=(l+r)//2
    if chk(mid):
        l=mid
    else:
        r=mid

AN=l

S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] > AN - la:
            rr = mi
        else:
            ll = mi
    c+=N-rr
    ans1=ans1+la*(N-rr)+S[N]-S[rr]

ans=ans1+(M-c)*AN
print(ans)

Solution (Python):










from bisect import bisect_right, bisect_left
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        
        return self.ls_accum[j] - self.ls_accum[i]


N, M = read_ints()
A = read_ints()
A.sort()  
A_reversed = list(reversed(A))
A_rev_acc = cumsum1d(A_reversed)


def is_ok(X):
    
    
    
    cnt = 0
    ans = 0
    for a in A:
        aa = X - a
        idx_reverse = N - bisect_left(A, aa)  
        
        cnt += idx_reverse
        ans += A_rev_acc.total(0, idx_reverse) + idx_reverse * a
    return cnt >= M, ans, cnt


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        flg, ans, cnt = is_ok(mid)
        if flg:
            ok = mid
            ans_true = ans  
            cnt_true = cnt
        else:
            ng = mid
    return ans_true, ok, cnt_true


ans_tmp, M_th_num, M_plus_alpha_th = \
    meguru_bisect(2 * 10 ** 5 + 1, 0)

print(ans_tmp - (M_plus_alpha_th - M) * M_th_num)

Solution (Python):










from bisect import bisect_right, bisect_left
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        
        return self.ls_accum[j] - self.ls_accum[i]


N, M = read_ints()
A = read_ints()
A.sort()  
A_reversed = list(reversed(A))
A_rev_acc = cumsum1d(A_reversed)


def is_ok(X):
    
    
    
    cnt = 0
    ans = 0
    for a in A:
        aa = X - a
        idx_reverse = N - bisect_left(A, aa)  
        
        cnt += idx_reverse
        ans += A_rev_acc.total(0, idx_reverse) + idx_reverse * a
    return cnt >= M, ans, cnt


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        flg, ans, cnt = is_ok(mid)
        if flg:
            ok = mid
            ans_true = ans  
            cnt_true = cnt
        else:
            ng = mid
    return ans_true, ok, cnt_true


ans_tmp, M_th_num, M_plus_alpha_th = \
    meguru_bisect(2 * 10 ** 5 + 1, 0)

print(ans_tmp - (M_plus_alpha_th - M) * M_th_num)

Solution (Python):
import bisect
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
r=[0]*(10**5+2)
for i in range(n):
    r[l[i]]+=1
for i in range(10**5+1):
    r[i+1]+=r[i]
ok=10**6
ng=0
while ok-ng>1:
    x=(ok+ng)//2
    k=0
    for i in range(n):
        if x-l[i]<0:
            k+=n
        elif x-l[i]>10**5+1:
            k+=0
        else:
            k+=n-r[x-l[i]]
    if k>=m:
        ng=x
    else:
        ok=x

p=[0]*(n+1)
for i in range(n):
    p[i+1]=p[i]+l[i]
ans=0
mi=0
for i in range(n):
    li=bisect.bisect_left(l,ok-l[i])
    ans+=l[i]*(n-li)+p[n]-p[li]
    mi+=n-li
print(ans-(mi-m)*ok)

Solution (Python):
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = n * n - a.searchsorted(m - a).sum()
    if res >= k:
        l = m
    else:
        r = m
b = np.array([0] * (n + 1))
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - a.searchsorted(l - x)
    ans += b[t] + x * t
    cnt += t
print(ans - (cnt - k) * l)

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

Solution (Python):
from itertools import groupby,accumulate
import bisect
n,m = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
le=len(A)

B=list(accumulate([0]+A))
ok=0 
ng=10**10 
ans=0
while 1<abs(ng-ok):
  mid=(ng+ok)//2
  ans=0
  cnt=0
  for i in range(le):
    x = mid-A[i]
    cnt1=int(bisect.bisect_left(A,x))
    cnt+=(le-cnt1)
    
  if cnt>=m:
    ok=mid
  else:
    ng=mid
cnt=0
for i in range(le):
  x=ok-A[i]
  cnt1=int(bisect.bisect_left(A,x))
  cnt+=le-cnt1
  ans+=A[i]*(le-cnt1)+B[n]-B[cnt1]
print(ans+(m-cnt)*ok)

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

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

"""
この問題の前半は、合計の幸福度Xが上位M個未満に入るかを判定する。
    -> Xに関する二分探索をすることで、上位から丁度M番目の幸福度がわかる！

これを判定するために、左手の握手先をfix(A[i]とする)して、
右手の幸福度が(X - A[i])以上であるものの個数を数える。
"""

def within(X, M):
    """
    幸福度がX以上上がるような握手の組がM個未満ならTrue、そうでなければFalseを返す
    """
    pair = 0
    for i in range(N):
        idx = bisect_left(A, X - A[i])
        pair += N - idx
    if pair < M:
        
        return True
    else:
        
        return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, M) == Trueになる最小のX
"""
leftX = 0
rightX = A[-1] * 2 + 1
while leftX != rightX:
    middleX = (leftX + rightX) // 2
    
    if within(middleX, M):
        rightX = middleX
    else:
        leftX = middleX + 1


"""
これより後半、幸福度の総和を求める。
前半同様に左手をfixした上で、両手の幸福度の合計がleftX以上になるときの幸福度を加算していく。
単純に右手に関してfor文を回して加算するとTLEなので、
右手の幸福度に関しては先に累積和を求めておく。
"""
S = list(itertools.accumulate(A))

happy = 0
times = 0
for i in range(N):
    idx = bisect_left(A, leftX - A[i])
    times += N - idx
    
    if idx != 0:
        happy += A[i] * (N - idx) + (S[-1] - S[idx - 1])
    else:
        happy += A[i] * (N - idx) + S[-1]
    
happy += (leftX - 1) * (M - times)

print(happy)

Solution (Python):
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
acum=[arr[0]]
for i in range(1,n):
  acum.append(acum[-1]+arr[i])
l=0
r=2*10**5+1
while r-l!=1:
  mid=(l+r)//2
  tmp=0
  cnt=0
  pos=n-1
  for i in range(n):
    while pos!=-1:
      if arr[i]+arr[pos]>=mid:
        cnt+=pos+1
        tmp+=arr[i]*(pos+1)+acum[pos]
        break
      else:
        pos-=1
        if pos==-1:
          break
  if cnt<=m:
    r=mid
  else:
    l=mid
tmp+=(m-cnt)*l
print(tmp)

Solution (Python):
def judge(k, N, A):
    p = N - 1
    t = 0
    for i in A:
        while p >= 0 and A[p] + i < k:
            p -= 1
        t += (p + 1)
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    r = 0
    p = N - 1
    k = sum(A)
    for i in A:
        while p >= 0 and A[p] + i < X :
            k -= A[p]
            p -= 1
        r += i * (p + 1) + k
    return r - (judge(X, N, A) - M) * X
print(main())

Solution (Python):
def judge(k, N, A):
    p = N - 1
    t = 0
    for i in A:
        while p >= 0 and A[p] + i < k:
            p -= 1
        t += (p + 1)
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    r = 0
    p = N - 1
    k = sum(A)
    for i in A:
        while p >= 0 and A[p] + i < X :
            k -= A[p]
            p -= 1
        r += i * (p + 1) + k
    return r - (judge(X, N, A) - M) * X
print(main())

Solution (Python):
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Solution (Python):
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Solution (Python):



import numpy as np

N,M = map(int,input().split())
A = np.array(input().split(),np.int64)

A = np.sort(A)
S = np.zeros(N+1,np.int64)
S[1:]= np.cumsum(A)

hi = 200001
lo = -1

while hi-lo > 1:
    mid = (hi+lo)//2
    above_mid = (N-np.searchsorted(A,mid-A,side='left')).sum()
    if above_mid >= M:
        lo = mid
    else:
        hi = mid

X = np.searchsorted(A,hi-A,side='left')

above_hi = (N-X).sum()
happiness = (S[-1]-S[X]).sum()
happiness += (A*(N-X)).sum()
happiness += (M-above_hi)*lo

print(happiness)