CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input=sys.stdin.readline
import bisect
n,k=list(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
	#mid以上はいくつあるか
	#答えはl以上r未満
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid
#lだとk個以上　rだとk個未満
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)


# Optimized solution
import bisect
n,k=list(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
	#mid以上はいくつあるか
	#答えはl以上r未満
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid
#lだとk個以上　rだとk個未満
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)
# Original solution
from bisect import bisect_left
from itertools import accumulate

N, M = list(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))

# Optimized solution
from bisect import bisect_left
from itertools import accumulate

N, M = list(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))
# Original solution
from bisect import bisect_left
from itertools import accumulate

N, M = list(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))

# Optimized solution
from itertools import accumulate

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

A.sort(reverse = True)
#print(A)

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
#print(ok)

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

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)
# Original solution
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 = list(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)
        im = judge(m - 1, N, A)
        ip = judge(m + 1, N, A)
        if i == M:
            X = m
            break
        if im == M:
            X = m - 1
            break
        if ip == M:
            X = m + 1
            break
        if i > M:
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            if im > M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(list(range(N))):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(list(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()))


# Optimized solution
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 = list(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(list(range(N))):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(list(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()))
# Original solution
def judge(k, N, A):
    t = 0
    s = N
    for i in A:
        for j in reversed(list(range(s))):
            if A[j] + i >= k:
                s = j + 1
                t += j + 1
                break
    return t
def main():
    N, M = list(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
    B = []
    tmp = 0
    for i in range(N):
        tmp += A[i]
        B.append(tmp)
    r = 0
    tot = 0
    s = N
    for i in A:
        for j in reversed(list(range(s))):
            if i + A[j] >= X:
                tot += j + 1
                s = j + 1
                r += i * (j + 1) + B[j]
                break
    return r - (tot - M) * X
print((main()))


# Optimized solution
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 = list(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()))
# Original solution
from itertools import accumulate
from heapq import heappush, heappop, heapify

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

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

def judge(p):
    j = N
    cnt = 0
    for al in A:
        while j > 0 and al+A[j-1] >= p:
            j -= 1
        cnt += N-j
    return cnt <= M

p = bisect(0, A[-1]*2+1, judge)

j = N
cnt = 0
res = 0
q = []
for al in A:
    while j > 0 and al+A[j-1] >= p:
        j -= 1
    cnt += N-j
    res += (N-j)*al + acc[-1]-acc[j]
    if j > 0:
        q.append((-(al+A[j-1]),al,j-1))

heapify(q)
for _ in range(M-cnt):
    p,al,j = heappop(q)
    res -= p
    if j > 0:
        heappush(q, (-(al+A[j-1]),al,j-1))

print(res)

# Optimized solution
from itertools import accumulate

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

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

def judge(p):
    j = N
    cnt = 0
    for al in A:
        while j > 0 and al+A[j-1] >= p:
            j -= 1
        cnt += N-j
    return cnt <= M

p = bisect(0, A[-1]*2+1, judge)

j = N
cnt = 0
res = 0
nv = 0
max2 = lambda x,y: x if x > y else y
for al in A:
    while j > 0 and al+A[j-1] >= p:
        j -= 1
    cnt += N-j
    res += (N-j)*al + acc[-1]-acc[j]
    if j > 0:
        nv = max2(nv, al+A[j-1])

res += nv*(M-cnt)
print(res)
# Original solution
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,m=MI()
    aa=LI()
    aa.sort(reverse=True)
    fin=set()
    hp=[]
    heappush(hp,[-aa[0]*2,0,0])
    fin.add((0,0))
    ans=0
    for _ in range(m):
        a,i,j=heappop(hp)
        ans-=a
        if i+1<n and (i+1,j) not in fin:
            heappush(hp,[-aa[i+1]-aa[j],i+1,j])
            fin.add((i+1,j))
        if j+1<n and (i,j+1) not in fin:
            heappush(hp,[-aa[i]-aa[j+1],i,j+1])
            fin.add((i,j+1))

    print(ans)

main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def ok(c):
        cnt = 0
        i = 0
        for a in aa[::-1]:
            while i < n and a + aa[i] >= c: i += 1
            cnt += i
            if cnt >= m: return True
        return False

    n, m = MI()
    aa = LI()
    aa.sort(reverse=True)
    # 握手の回数がm以上になるような、1回の握手の幸福度の最低値を求める
    l = aa[-1] * 2 - 1
    r = aa[0] * 2 + 1
    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            l = c
        else:
            r = c
    min_once = l
    # 幸福度がmin_once以上になる握手の総和を求める
    ans = 0
    i = 0
    s = 0
    cnt = 0
    for a in aa[::-1]:
        while i < n and a + aa[i] >= min_once:
            s += aa[i]
            i += 1
        ans += s + i * a
        cnt += i
    # 握手の回数がmを越えたときはその分の幸福度を引く
    if cnt - m:
        ans -= min_once * (cnt - m)
    print(ans)

main()
# Original solution
n,m = list(map(int, input().split()))
A = sorted(list(map(int, input().split())),reverse=True)

def cnt(x):
    c = 0
    for j in range(len(A)):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += 1
            i += 1
    return c

def happiness(x):
    c = 0
    for j in range(len(A)):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += A[j]+A[i]
            i += 1
    return c

def binary_search(l, r):
    mid = (l+r)//2
    c = cnt(mid)
    if c < m:
        return binary_search(l, mid)   
    else:
        if l == mid:
            return(l, c-m)
        return binary_search(mid, r)

x, dm = binary_search(0, A[0]*2+1)
print((happiness(x)-dm*x))

# Optimized solution
N, M = list(map(int, input().split()))
A = sorted(list(map(int,input().split())), reverse=True)

# jとの組み合わせがx以上になるiの個数
def combinations(x):
  s = 0
  i = 0
  for j in reversed(list(range(N))):
    while i<N and A[i]+A[j]>=x:
      i += 1
    s += i
  return s
 
#↑のような組み合わせの合計幸福度
def koufukudo(x):
  s = 0
  si = 0
  i = 0
  for j in reversed(list(range(N))):
    while i<N and A[i]+A[j]>=x:
      si += A[i]
      i += 1
    s += si + A[j]*i  
  return s
 
#
def bsearch(l, u):
  m = (l+u)//2
  c = combinations(m)
#   print(f"m{m}, c{c},c-M{c-M}")
  if c<M:
    return bsearch(l, m)
  else:
    if l==m:
      return (l, c-M)
    return bsearch(m, u)
 
x, dm = bsearch(0, A[0]*2+1)
print((koufukudo(x)-dm*x))
# Original solution
import heapq


n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)

idx_dict = {}
for i in range(n):
    idx_dict[i] = i+1

ans = [A[i]+A[i] for i in range(n)]
candidates = [[-(A[i]+A[i+1]), i] for i in range(n-1)]
heapq.heapify(candidates)

for i in range(m//2):
    if not candidates:
        break
    num, idx = heapq.heappop(candidates)
    ans.append(-num)
    ans.append(-num)
    idx_dict[idx] += 1
    new_pair = idx_dict[idx]
    if new_pair >= n:
        continue
    candidate = A[idx] + A[new_pair]
    heapq.heappush(candidates, [-candidate, idx])

ans.sort(reverse=True)
print((sum(ans[:m])))

# Optimized solution
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
cumsumA = []

total = 0
for a in A:
    total += a
    cumsumA.append(total)
cumsumA.append(0)

l = 0
r = 10 ** 6
while l + 1 < r:
    num = (l+r)//2
    pair_idx = n-1
    count = 0
    for a in A:
        while a + A[pair_idx] < num and pair_idx >= 0:
            pair_idx -= 1

        count += pair_idx+1

    if count < m:
        r = num
        continue
    elif count >= m:
        l = num


ans = 0
count = 0
num = l
pair_idx = n-1
for a in A:
    while a + A[pair_idx] < num and pair_idx >= 0:
        pair_idx -= 1

    count += pair_idx+1
    ans += cumsumA[pair_idx] + a*(pair_idx+1)

diff = count - m
ans -= num * diff
print(ans)
# Original solution
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
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:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            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])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        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))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
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:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            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])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            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))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()
# Original solution
from bisect import bisect_left

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

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**12
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

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


# Optimized solution
from bisect import bisect_left

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

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = A[-1] * 2 + 100
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)
# Original solution
from bisect import bisect_left
from itertools import accumulate
N,M,*A = list(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)

# Optimized solution
from bisect import bisect_left
from itertools import accumulate
N,M,*A = list(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)
# Original solution
import bisect

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

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt


l=0
h=10**15+3
mid=(l+h)//2

while l+1<h:
  mid=(l+h)//2
  if hand(mid)<m:
    h=mid
  else:
    l=mid

B=A[::-1]

for i in range(n-1):
  B[i+1]+=B[i]

B=B[::-1]

ans=0
cnt=0


for i in range(n):
  y=l-A[i]+1
  index=bisect.bisect_left(A,y)
  if n==index:
    continue
  else:
    ans+=(n-index)*A[i]+B[index]
    cnt+=(n-index)

ans+=(m-cnt)*l
print(ans)
  

  
  

# Optimized solution
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

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

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=10**15+3
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B=A[::-1]
  
  for i in range(n-1):
    B[i+1]+=B[i]
  
  B=B[::-1]
  
  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()
# Original solution
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

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

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()
  

  
  

# Optimized solution
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

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

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[-i-1]
    k=n-bisect.bisect_left(A,p)
    if k==0:
      break
    cnt+=k
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()