import sys

from itertools import accumulate



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

a.sort()



ma = a[-1]

cnt = [0] * (ma + 1)

cur = ma

for i in range(n-1, -1, -1):

    if a[i] == cur:

        cnt[cur] += 1

    else:

        while True:

            cur -= 1

            cnt[cur] = cnt[cur+1]

            if cur == a[i]:

                cnt[cur] += 1

                break

for i in range(cur-1, -1, -1):

    cnt[i] = cnt[i+1]





def possible(border):

    pair_cnt = 0

    for i in range(n):

        aj = border - a[i]

        if aj < 0:

            aj = 0

        elif aj > ma:

            continue

        pair_cnt += cnt[aj]

    return pair_cnt >= m



def main():

    s = [0] + list(accumulate(a[::-1]))

    

    lo = 1; hi = a[-1] * 2 + 1

    while lo + 1 < hi:

        border = (lo + hi) // 2

        if possible(border):

            lo = border

        else:

            hi = border

    res = lo

    ans = 0

    minimum = float('inf')

    pair_cnt = 0

    for i in range(n):

        aj = res - a[i]

        if aj < 0:

            aj = 0

        elif aj > ma:

            continue

        c = cnt[aj]

        ans += s[c] + a[i] * c

        pair_cnt += c

        minimum = min(minimum, a[i] + a[-c])



    ans -= minimum * (pair_cnt - m)

    return ans



if __name__ == '__main__':

    ans = main()

    print(ans)
import sys

import numpy as np 



I = np.array(sys.stdin.read().split(), dtype=np.int64)

n, m = I[:2]

a = I[2:]

a.sort()

ma = a[-1]

cnt = np.bincount(a, minlength=ma+2)

cnt_not_less_than = np.cumsum(cnt[::-1])[::-1]



right = a[:, None]

def possible(border):

    left = border - right

    left = np.maximum(left, 0)

    left = np.minimum(left, ma+1)

    pair_cnt = np.sum(cnt_not_less_than[left])

    return pair_cnt >= m



def main():

    lo = 1; hi = ma * 2 + 1

    while lo + 1 < hi:

        border = (lo + hi) // 2

        if possible(border):

            lo = border

        else:

            hi = border



    res = lo

    left = res - right

    left = np.maximum(left, 0)

    left = np.minimum(left, ma+1)

    c = cnt_not_less_than[left[left != ma+1]]

    pair_cnt = np.sum(c)

    minimum = np.amin(right[left != ma + 1] + a[-c])



    s = np.cumsum(a[::-1])

    ans = np.sum(s[c-1] + right[left != ma+1] * c) - minimum * (pair_cnt - m)

    return ans



if __name__ == '__main__':

    ans = main()

    print(ans)
import sys
from itertools import accumulate

n, m, *a = list(map(int, sys.stdin.read().split()))
a.sort()
ma = a[-1]
cnt = [0] * (ma + 1)
cur = ma
for i in range(n - 1, -1, -1):
    if a[i] == cur:
        cnt[cur] += 1
    else:
        while True:
            cur -= 1
            cnt[cur] = cnt[cur + 1]
            if cur == a[i]:
                cnt[cur] += 1
                break
for i in range(cur - 1, -1, -1):
    cnt[i] = cnt[i + 1]


def possible(border):
    pair_cnt = 0
    for i in range(n):
        aj = border - a[i]
        if aj < 0:
            aj = 0
        elif aj > ma:
            continue
        pair_cnt += cnt[aj]
    return pair_cnt >= m


def main():
    s = [0] + list(accumulate(a[::-1]))
    lo = 1
    hi = a[-1] * 2 + 1
    while lo + 1 < hi:
        border = (lo + hi) // 2
        if possible(border):
            lo = border
        else:
            hi = border
    res = lo
    ans = 0
    minimum = float("inf")
    pair_cnt = 0
    for i in range(n):
        aj = res - a[i]
        if aj < 0:
            aj = 0
        elif aj > ma:
            continue
        c = cnt[aj]
        ans += s[c] + a[i] * c
        pair_cnt += c
        minimum = min(minimum, a[i] + a[-c])
    ans -= minimum * (pair_cnt - m)
    return ans


if __name__ == "__main__":
    ans = main()
    print(ans)

import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m = I[:2]
a = I[2:]
a.sort()
ma = a[-1]
cnt = np.bincount(a, minlength=ma + 2)
cnt_not_less_than = np.cumsum(cnt[::-1])[::-1]
right = a[:, None]


def possible(border):
    left = border - right
    left = np.maximum(left, 0)
    left = np.minimum(left, ma + 1)
    pair_cnt = np.sum(cnt_not_less_than[left])
    return pair_cnt >= m


def main():
    lo = 1
    hi = ma * 2 + 1
    while lo + 1 < hi:
        border = (lo + hi) // 2
        if possible(border):
            lo = border
        else:
            hi = border
    res = lo
    left = res - right
    left = np.maximum(left, 0)
    left = np.minimum(left, ma + 1)
    c = cnt_not_less_than[left[left != ma + 1]]
    pair_cnt = np.sum(c)
    minimum = np.amin(right[left != ma + 1] + a[-c])
    s = np.cumsum(a[::-1])
    ans = np.sum(s[c - 1] + right[left != ma + 1] * c) - minimum * (pair_cnt - m)
    return ans


if __name__ == "__main__":
    ans = main()
    print(ans)

-from itertools import accumulate +import numpy as np -n, m, *a = list(map(int, sys.stdin.read().split())) +I = np.array(sys.stdin.read().split(), dtype=np.int64) +n, m = I[:2] +a = I[2:] -cnt = [0] * (ma + 1) -cur = ma -for i in range(n - 1, -1, -1): -    if a[i] == cur: -        cnt[cur] += 1 -    else: -        while True: -            cur -= 1 -            cnt[cur] = cnt[cur + 1] -            if cur == a[i]: -                cnt[cur] += 1 -                break -for i in range(cur - 1, -1, -1): -    cnt[i] = cnt[i + 1] +cnt = np.bincount(a, minlength=ma + 2) +cnt_not_less_than = np.cumsum(cnt[::-1])[::-1] +right = a[:, None] -    pair_cnt = 0 -    for i in range(n): -        aj = border - a[i] -        if aj < 0: -            aj = 0 -        elif aj > ma: -            continue -        pair_cnt += cnt[aj] +    left = border - right +    left = np.maximum(left, 0) +    left = np.minimum(left, ma + 1) +    pair_cnt = np.sum(cnt_not_less_than[left]) -    s = [0] + list(accumulate(a[::-1])) -    hi = a[-1] * 2 + 1 +    hi = ma * 2 + 1 -    ans = 0 -    minimum = float("inf") -    pair_cnt = 0 -    for i in range(n): -        aj = res - a[i] -        if aj < 0: -            aj = 0 -        elif aj > ma: -            continue -        c = cnt[aj] -        ans += s[c] + a[i] * c -        pair_cnt += c -        minimum = min(minimum, a[i] + a[-c]) -    ans -= minimum * (pair_cnt - m) +    left = res - right +    left = np.maximum(left, 0) +    left = np.minimum(left, ma + 1) +    c = cnt_not_less_than[left[left != ma + 1]] +    pair_cnt = np.sum(c) +    minimum = np.amin(right[left != ma + 1] + a[-c]) +    s = np.cumsum(a[::-1]) +    ans = np.sum(s[c - 1] + right[left != ma + 1] * c) - minimum * (pair_cnt - m)