CodeEff/ECCO huggingface dataset:
# 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-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()
  

  
  

# 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
    if cnt>=m:
      break
  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()
# Original solution
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

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

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        flg = False
        for a2 in A2:
            if cnt >= M:
                break
            if a1 + a2 < m:
                break
            else:
                flg = True
                cnt += 1
        if not flg:
            break
    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
# print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt
    if total_cnt >= M:
        break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)


# Optimized solution
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

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

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        tmp = bisect_left(A, m - a1)
        if tmp == N: break
        cnt += N - tmp

    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
# print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a
    if min_right > A[-1]:
        continue

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt

    # if total_cnt >= M:
    #     break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)
# Original solution
import sys

input=sys.stdin.readline

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

# Optimized solution
N,M=list(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)
# Original solution
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

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

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

    def value(v):
        if sum([n-bl(a, v-a[i]) for i in range(n)]) >= m:
            return True
        else:
            return False

    b = b_search(0, 10**15, value)
    c = sum([n-bl(a, b-a[i]) for i in range(n)])-m
    ans = -c*b
    for i in range(n):
        d = bl(a, b-a[i])
        ans += aa[n]-aa[d]+(n-d)*a[i]
    print(ans)


main()


# Optimized solution
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

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

    ok = 0
    ng = 10**15
    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 += aa[n]-aa[d]+(n-d)*a[i]
    print(ans)


main()
# Original solution
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 = list(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
            # [j,N)の要素数

        return ret

    x = binary_search(ok=A[-1] * 2 + 1, ng=0, is_ok=lambda x: count(x) < M)
    # 幸福度の総和がX以上のペア数がM未満となる最大のX

    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()


# Optimized solution
# 過去の提出を見ながら解いた

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

    def count(mid) -> int:
        cnt = 0  # (i,j)>=mid の個数
        j = N  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
        for i in range(N):
            while j > 0 and a[i] + a[j - 1] >= mid:
                j -= 1
            # j==0 or a[i]+a[j]>=mid
            # j==0
            # 現在のiに対しすべてのaの要素が相方になる。
            # 一度そのようなiに達したら、それ以降のiはすべてこの条件を満たす。
            cnt += N - j  # iに対し[j,N)が相方になる
        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  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
    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]  # i側の寄与=ペア数,j側の寄与=acc
    ans += (ma - 1) * (M - count(ma))  # ペア和maではMペア組めないが、ma-1で埋められる

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
#import sys
#sys.setrecursionlimit(10**7)
#from functools import reduce
#from fractions import gcd


# input
n, m = list(map(int, list(input().split())))
alist = list(map(int, input().split()))

# process
blist=[]
for i in alist:
    for j in alist:
        blist.append(i+j)

blist.sort(reverse=True)

ans = 0
for i in range(m):
    ans += blist[i]    

# output
print(ans)

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

# process
A.sort(reverse=True)

# 1回の握手の幸福度がx以上となるものの数、幸福度の合計を求める
def calc(x):
    count, sum = 0, 0

    j, t = 0, 0
    for i in reversed(list(range(N))):
        while j < N and A[i]+A[j] >= x:
            t += A[j]
            j += 1
        count += j
        sum += A[i]*j + t
    
    return (count, sum)

# 2分探索で答えを求める
def binary_search(x, y):
    mid = (x+y)//2

    count, sum = calc(mid)
    
    if count < M:
        return binary_search(x, mid)
    else:
        if x == mid:
            print((sum-(count-M)*mid))
        else:
            return binary_search(mid, y)

# 実行
binary_search(0, A[0]*2+1)
# Original solution

from bisect import bisect_left, bisect_right
from itertools import accumulate
def resolve():
    def shake_cnt(x):
        cnt = 0
        pos = 0
        for i in range(N):
            pos = bisect_left(A, x - A[i])
            cnt += N - pos
        return cnt < M # X以上の和がM個未満かどうか

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

    # 終了時にngにX-1,okにXが入っている。
    ng = 0
    ok = 10 ** 6
    while abs(ok - ng) > 1:
        mid = (ok + ng)//2
        if shake_cnt(mid):
            ok = mid
        else:
            ng = mid

    acc = [0] + list(accumulate(A))
    ans = 0
    for i in range(N):
        pos = bisect_right(A, ng - A[i])
        cnt = N - pos
        ans += cnt * A[i] + (acc[N] - acc[pos])
        M -= cnt
    ans += M * ng
    print(ans)


if __name__ == "__main__":
    resolve()


# Optimized solution

from bisect import bisect_left
from itertools import accumulate
def resolve():
    def getCount(x):
        count = 0
        for Ai in A:
            idx = bisect_left(A, x - Ai)
            count += N - idx
        return count >= M


    N, M = list(map(int, input().split()))
    A = sorted(map(int, input().split()))
    A_r = A[::-1]
    B = [0] + list(accumulate(A_r))

    MIN = 0
    MAX = 2 * 10 ** 5 + 1
    while MAX - MIN > 1:
        MID = (MIN + MAX) // 2
        if getCount(MID):
            MIN = MID
        else:
            MAX = MID

    ans = 0
    count = 0

    for Ai in A_r:
        idx = bisect_left(A, MIN - Ai)
        ans += Ai * (N - idx) + B[N - idx]
        count += N - idx
    print((ans - (count - M) * MIN))


if __name__ == "__main__":
    resolve()
# Original solution

from bisect import bisect_left
from itertools import accumulate

def resolve():
    def getCount(x):
        cnt = 0
        for a in A:
            # X未満の個数
            idx = bisect_left(A, x - a)
            # X以上の個数
            cnt += N - idx
        # X以上を使う！と決めた時、M個以上になるか
        return cnt >= M

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

    ng = 10 ** 18
    ok = 0
    # X以上を使う！と決めるとX以上の個数が自明にわかる。
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if getCount(mid):
            ok = mid
        else:
            ng = mid

    # M個以上あることがわかれば、Mよりも余分な数(同じ値が複数ある場合)
    # はすべてXである事がわかるため、差分だけ引けば良い。
    B = [0] + list(accumulate(A))
    ans = 0
    cnt = 0
    for i in range(N):
        idx = bisect_left(A, ok - A[i])
        ans += B[N] - B[idx] + A[i] * (N - idx)
        cnt += N - idx

    rest = (cnt - M) * ok
    print((ans - rest))


if __name__ == "__main__":
    resolve()

# Optimized solution

from bisect import bisect_left
from itertools import accumulate

def resolve():
    def getCount(x):
        cnt = 0
        for a in A:
            # X未満の個数
            idx = bisect_left(A, x - a)
            # X以上の個数
            cnt += N - idx
        # X以上を使う！と決めた時、M個以上になるか
        return cnt >= M

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

    ng = 10 ** 9
    ok = 0
    # X以上を使う！と決めるとX以上の個数が自明にわかる。
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if getCount(mid):
            ok = mid
        else:
            ng = mid

    # M個以上あることがわかれば、Mよりも余分な数(同じ値が複数ある場合)
    # はすべてXである事がわかるため、差分だけ引けば良い。
    B = [0] + list(accumulate(A))
    ans = 0
    cnt = 0
    for i in range(N):
        idx = bisect_left(A, ok - A[i])
        ans += B[N] - B[idx] + A[i] * (N - idx)
        cnt += N - idx

    rest = (cnt - M) * ok
    print((ans - rest))


if __name__ == "__main__":
    resolve()
# Original solution
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# 右手と左手(a,b)の和がx以上となる組の数
def calc(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    for a in A:
        # 式変形： a + b >= x → b >= x - a
        ans += N - bisect_left(A, x - a)
    return ans >= M

N, M = MAP()
A = LIST()

A.sort()
res = bisearch_max(0, INF, calc)

ans = m = 0
acc = [0] + list(accumulate(A))
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    # 幸福度
    ans += a * cnt + (acc[N] - acc[idx])
    # 握手の回数
    m += cnt

# 同値でMを超えた分の調整
ans -= res * (m - M)
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# 右手と左手(a,b)の和がx以上となる組の数
def calc(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    for a in A:
        # 式変形： a + b >= x → b >= x - a
        ans += N - bisect_left(A, x - a)
    return ans >= M

N, M = MAP()
A = LIST()

A.sort()
res = bisearch_max(0, 10**10+1, calc)

ans = m = 0
acc = [0] + list(accumulate(A))
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    # 幸福度
    ans += a * cnt + (acc[N] - acc[idx])
    # 握手の回数
    m += cnt

# 同値でMを超えた分の調整
ans -= res * (m - M)
print(ans)
# Original solution
import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = list(map(int, input().split()))
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    count_l = 0
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: 
            l = m
            count_l = count
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)  
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        if count_l > M:
            double = bisect_left(A, h - a)
            for k in range(j, min(N - 1, double + 1)):
                heapq.heappush(Q, a + A[k])

    if count > M:
        for _ in range(count - M):
            minus = heapq.heappop(Q)
            total -= minus

    print(total)

    return 0

if __name__ == "__main__":
    solve()


# Optimized solution
import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = list(map(int, input().split()))
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: 
            l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    min_out = 10000000
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)  
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        if 0 <= j < N: min_out = min(min_out, a + A[j])

    if count > M:
        total -= min_out * (count - M)

    print(total)

    return 0

if __name__ == "__main__":
    solve()
# Original solution
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)


# Optimized solution
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)
# Original solution
from bisect import bisect_left as bl
from itertools import accumulate as ac
n,m=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
s=[0]+list(ac(a[::-1]))
l,r=2*a[-1]*(n**2)+1,0
while l-r>1:
    t=(l+r)//2
    p=0
    for i in range(n):
        x=bl(a,t-a[i])
        p+=n-x
    if p<m:
        l=t
    else:
        r=t
c,d=0,0
w=0
for i in range(n):
    g=bl(a,r-a[i])
    x=n-g
    c+=s[x]+x*a[i]
    w+=x
print((c-r*max(0,(w-m))))

# Optimized solution
from bisect import bisect_left as bl
from itertools import accumulate as ac
n,m=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
s=[0]+list(ac(a[::-1]))
l,r=2*a[-1]*(n**2)+1,0
while l-r>1:
    t=(l+r)//2
    p=0
    for i in range(n-1,-1,-1):
        if a[i]+a[-1]>=t:
            x=bl(a,t-a[i])
            p+=n-x
        else:
            break
    if p<m:
        l=t
    else:
        r=t
c,d=0,0
w=0
for i in range(n-1,-1,-1):
    if a[i]+a[-1]>=r:
        g=bl(a,r-a[i])
        x=n-g
        c+=s[x]+x*a[i]
        w+=x
    else:
        break
print((c-r*max(0,(w-m))))