AtCoder Beginner Contest 149 - Handshake

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-----
5 3
10 14 19 34 33

-----Sample Output-----
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.

Difficulty: MEDIUM

Starter code:

Solutions:
from itertools import accumulate
from bisect import *
(n, m, *a) = map(int, open(0).read().split())
a = [-x for x in a]
a.sort()
acc = list(accumulate(a)) + [0]
l = 0
r = 2 * 10 ** 5 + 1
while r - l > 1:
	mid = (l + r) // 2
	border = n - 1
	cnt = 0
	for x in a:
		while x + a[border] > -mid:
			border -= 1
			if border < 0:
				break
		if border < 0:
			break
		cnt += border + 1
		if cnt >= m:
			break
	if cnt >= m:
		l = mid
	else:
		r = mid
ans = tot = 0
for x in a:
	b = bisect(a, -l - x)
	tot += b
	ans += acc[b - 1] + x * b
ans += l * (tot - m)
print(-ans)


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

def isOver(a, n, x):
	cnt = 0
	for i in range(n):
		cnt += n - bisect_left(a, x - a[i])
	return cnt

def calX(a, n, m, l, r):
	while r - l > 1:
		x = (l + r) // 2
		if isOver(a, n, x) >= m:
			l = x
		else:
			r = x
	return l
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = [0] * (n + 1)
for i in range(n):
	s[i + 1] = s[i] + a[i]
x = calX(a, n, m, a[0] * 2, a[n - 1] * 2)
out = 0
for i in range(n):
	idx = bisect_left(a, x - a[i])
	out += s[n] - s[idx] + a[i] * (n - idx)
out -= (isOver(a, n, x) - m) * x
print(out)


from bisect import bisect_left
INF = int(1000000000.0)

def main():
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	ac = [0]
	for i in range(n):
		ac.append(ac[i] + a[i])

	def chk(x):
		cnt = 0
		for i in range(n):
			pos = bisect_left(a, x - a[i])
			cnt += n - pos
		return cnt < m
	l = 0
	r = INF
	while r - l > 1:
		mid = (l + r) // 2
		if chk(mid):
			r = mid
		else:
			l = mid
	cnt = 0
	sgm = 0
	for i in range(n):
		pos = bisect_left(a, r - a[i])
		cnt += n - pos
		sgm += a[i] * (n - pos) + (ac[n] - ac[pos])
	print(sgm + (m - cnt) * l)
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(x):
	c = 0
	for y in a:
		ok = N
		ng = -1
		while ok - ng > 1:
			m = (ok + ng) // 2
			if a[m] + y >= x:
				ok = m
			else:
				ng = m
		c += N - ok
	return c >= M
ok = 0
ng = 10 ** 6
while ng - ok > 1:
	m = (ok + ng) // 2
	if check(m):
		ok = m
	else:
		ng = m
l = ok + 1
cs = [0] * (N + 1)
for i in range(N):
	cs[i + 1] = cs[i] + a[i]
res = 0
c = 0
for x in a:
	ok = N
	ng = -1
	while ok - ng > 1:
		m = (ok + ng) // 2
		if a[m] + x >= l:
			ok = m
		else:
			ng = m
	c += N - ok
	res += cs[-1] - cs[ok] + x * (N - ok)
print(res + (l - 1) * (M - c))


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


from bisect import bisect_left, bisect_right
maxA = 10 ** 5
(N, M) = map(int, input().split())
As = list(map(int, input().split()))
As.sort()

def isOK(v):
	num = 0
	for A in As:
		i = bisect_left(As, v - A)
		num += N - i
	return num >= M
(ng, ok) = (2 * maxA + 1, 0)
while abs(ok - ng) > 1:
	mid = (ng + ok) // 2
	if isOK(mid):
		ok = mid
	else:
		ng = mid
accRevAs = [As[-1]]
for A in reversed(As[:-1]):
	accRevAs.append(accRevAs[-1] + A)
accRevAs.reverse()
v = ok
ans = 0
numGt = 0
for A in As:
	iR = bisect_right(As, v - A)
	if iR < N:
		ans += accRevAs[iR] + A * (N - iR)
	numGt += N - iR
ans += v * (M - numGt)
print(ans)


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


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
	(N, M) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort()
	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)

def __starting_point():
	resolve()
__starting_point()


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

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

def binary_search():
	(l, r) = (0, 10 ** 11)
	while l <= r:
		mid = (l + r) // 2
		if judge(mid):
			l = mid + 1
		else:
			r = mid - 1
	return r
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0]
for Ai in A:
	acc.append(acc[-1] + Ai)
ans = 0
cnt = 0
for i in range(N):
	idx = bisect_left(A, border - A[i] + 1)
	ans += A[i] * (N - idx) + acc[N] - acc[idx]
	cnt += N - idx
ans += (M - cnt) * border
print(ans)


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

	def count(mid) -> int:
		cnt = 0
		j = N
		for i in range(N):
			while j > 0 and a[i] + a[j - 1] >= mid:
				j -= 1
			cnt += N - j
		return cnt

	def binary_search(*, ok: int, ng: int, is_ok: 'function') -> int:
		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
	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]
	ans += (ma - 1) * (M - count(ma))
	print(ans)

def __starting_point():
	main()
__starting_point()


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)


from itertools import accumulate
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(accumulate(A))

def pnum(X, N, A, B):
	l = 0
	r = N - 1
	num = 0
	s = 0
	while l != N and r != -1:
		if A[l] + A[r] >= X:
			num += r + 1
			s += A[l] * (r + 1) + B[r]
			l += 1
		else:
			r -= 1
	return (num, s)
l = 0
r = A[0] * 2 + 1
while r - l > 1:
	m = (r + l) // 2
	(a, b) = pnum(m, N, A, B)
	if a < M:
		r = m
	else:
		l = m
		num = a
		ans = b
if num > M:
	ans -= l * (num - M)
print(ans)


import bisect
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
C = [0] * (10 ** 5 * 2 + 1)
for a in A:
	C[a] += 1
for i in range(1, len(C)):
	C[i] += C[i - 1]

def pattern_num_ge_x(x):
	p = 0
	for a in A:
		p += N - (C[x - a - 1] if x - a - 1 >= 0 else 0)
	return p
l = -1
r = 10 ** 5 * 2 + 1
while r - l > 1:
	m = (r + l) // 2
	if pattern_num_ge_x(m) < M:
		r = m
	else:
		l = m
S = [0] + list(reversed(A[:]))
for i in range(1, N + 1):
	S[i] += S[i - 1]
ans = 0
for a in A:
	idx = bisect.bisect_left(A, r - a)
	ans += a * (N - idx) + S[N - idx]
	M -= N - idx
ans += l * M
print(ans)


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

def is_ok(x):
	cnt = 0
	for (i, a) in enumerate(A):
		j = bisect.bisect_left(A, x - a)
		cnt += n - j
	if cnt >= m:
		return True
	else:
		return False
l = 0
r = 2 * 10 ** 5 + 1
while l + 1 < r:
	c = (l + r) // 2
	if is_ok(c):
		l = c
	else:
		r = c
from itertools import accumulate
B = [0] + A
B = list(accumulate(B))
ans = 0
cnt = 0
for a in A:
	j = bisect.bisect_left(A, l - a)
	cnt += n - j
	ans += B[-1] - B[j] + a * (n - j)
ans -= (cnt - m) * l
print(ans)


import bisect
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a_cum = [0 for _ in range(n + 1)]
for i in range(n):
	a_cum[i + 1] = a_cum[i] + a[i]
(l, r) = (0, 10 ** 6)
while r - l > 1:
	x = (l + r) // 2
	cnt = 0
	for i in range(n):
		idx = bisect.bisect_left(a, x - a[i])
		cnt += n - idx
	if cnt >= m:
		l = x
	else:
		r = x
ans = 0
cnt = 0
for i in range(n):
	idx = bisect.bisect_left(a, l - a[i])
	cnt += n - idx
	ans += a_cum[n] - a_cum[idx]
	ans += a[i] * (n - idx)
if cnt > m:
	ans -= l * (cnt - m)
print(ans)


from bisect import bisect_right
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = [-a for a in A]
B.sort()
C = [0]
for b in B:
	C.append(C[-1] + b)

def is_ok(m):
	p = 0
	for b in B:
		i = bisect_right(B, -b - m)
		p += i
		if p >= M:
			return True
	return False
ok = 0
ng = 2 * 10 ** 5 + 1
while ng - ok > 1:
	m = (ok + ng) // 2
	if is_ok(m):
		ok = m
	else:
		ng = m

def calc(m):
	p = s = 0
	for b in B:
		i = bisect_right(B, -b - m)
		p += i
		s += C[i] + i * b
	return (p, -s)
(p1, s1) = calc(ok)
(p2, s2) = calc(ng)
ans = (s1 - s2) // (p1 - p2) * (M - p2) + s2
print(ans)


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

def judge(x):
	cnt = 0
	for Ai in A:
		cnt += N - bisect_left(A, x - Ai + 1)
	return cnt < M

def binary_search():
	(l, r) = (0, 2 * max(A))
	while l <= r:
		m = (l + r) // 2
		if judge(m):
			r = m - 1
		else:
			l = m + 1
	return l
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0] * (N + 1)
for i in range(N):
	acc[i + 1] = acc[i] + A[i]
cnt = 0
ans = 0
for Ai in A:
	j = bisect_left(A, border - Ai + 1)
	cnt += N - j
	ans += (N - j) * Ai + acc[N] - acc[j]
ans += (M - cnt) * border
print(ans)


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


import sys
input = sys.stdin.readline
mm = 10 ** 10
k = mm.bit_length()
K = 1 << k
nu = lambda L: int(''.join([bin(K + a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + '0'
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i + 1) * k - 1:-i * k - 1] for i in range(200001)]]
(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [0] * 100001
for i in a:
	b[i] += 1
c = li(st(nu(b) * nu(b)))
ans = 0
for i in range(200001)[::-1]:
	if c[i] > 0:
		p = min(m, c[i])
		m -= p
		ans += i * p
		if m == 0:
			break
print(ans)


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)

def __starting_point():
	main()
__starting_point()


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


from bisect import bisect_left
(N, M) = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

def calc(m):
	c = 0
	for i in range(N):
		c += N - bisect_left(A, m - A[i])
	return c
(ng, ok) = (0, A[-1] * 2 + 1)
while ok - ng > 1:
	m = (ok + ng) // 2
	if calc(m) <= M:
		ok = m
	else:
		ng = m
S = [A[0]]
for i in range(1, N):
	S.append(S[-1] + A[i])
S.append(0)
S.append(0)
all = sum(A)
ret = 0
for i in range(N):
	ret += all - S[bisect_left(A, ng - A[i]) - 1]
	ret += A[i] * (N - bisect_left(A, ng - A[i]))
ret -= (calc(ng) - M) * ng
print(ret)


from bisect import bisect_left
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(mid):
	cnt = 0
	for i in range(n):
		s = mid - a[i]
		cnt += n - bisect_left(a, s)
		if cnt >= m:
			return True
	return False
left = 0
right = 10 ** 11
while right - left > 1:
	mid = (right + left) // 2
	if check(mid):
		left = mid
	else:
		right = mid
cs = [0]
for i in reversed(range(n)):
	cs.append(cs[-1] + a[i])
ans = 0
cnt = 0
for i in range(n):
	j = n - bisect_left(a, right - a[i])
	ans += j * a[i] + cs[j]
	cnt += j
ans += (m - cnt) * left
print(ans)


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

def judge(x):
	cnt = 0
	for Ai in A:
		cnt += N - bisect_left(A, x - Ai)
	return cnt >= M

def binary_search():
	(l, r) = (0, 10 ** 10 + 100)
	while l <= r:
		m = (l + r) // 2
		if judge(m):
			l = m + 1
		else:
			r = m - 1
	return r
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
acc = [0]
for Ai in A:
	acc.append(acc[-1] + Ai)
b = binary_search()
ans = 0
cnt = 0
for Ai in A:
	i = bisect_left(A, b + 1 - Ai)
	ans += (N - i) * Ai + acc[N] - acc[i]
	cnt += N - i
ans += (M - cnt) * b
print(ans)


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

def check(X):
	i = N - 1
	n = 0
	for ax in A:
		while i >= 0 and A[i] + ax < X:
			i -= 1
		n += i + 1
	return n >= M
min_ng = 10 ** 6
max_ok = 0
while min_ng - max_ok > 1:
	tgt = (min_ng + max_ok) // 2
	if check(tgt):
		max_ok = tgt
	else:
		min_ng = tgt
i = N - 1
k = sum(A)
ans = 0
n = 0
for ax in A:
	while i >= 0 and A[i] + ax < max_ok:
		k -= A[i]
		i -= 1
	ans += k + ax * (i + 1)
	n += i + 1
print(ans - max_ok * (n - M))


import bisect
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
cumA = [0] * (n + 1)
for i in range(n):
	cumA[i + 1] = cumA[i] + A[i]
ans = 0
(ok, ng) = (0, 1000000.0)
while abs(ng - ok) > 1:
	mid = (ok + ng) // 2
	t = 0
	for a in A:
		t += n - bisect.bisect_left(A, mid - a)
	if t >= m:
		ok = mid
	else:
		ng = mid
ans = 0
t = 0
for i in range(n):
	k = bisect.bisect_left(A, ng - A[i])
	t += n - k
	ans += cumA[n] - cumA[k] + (n - k) * A[i]
ans += ok * (m - t)
print(int(ans))


import bisect
import sys
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
L = A[:]
R = A[:]
for i in range(N - 1):
	L[i + 1] += L[i]
	R[-i - 2] += R[-i - 1]

def func(l, r):
	if r - l == 1:
		return l
	m = (l + r) // 2
	count = 0
	for i in A:
		count += N - bisect.bisect_left(A, m - i)
	if count >= M:
		return func(m, r)
	return func(l, m)
f = func(0, 10 ** 6)
ans = 0
count = 0
for p in range(N):
	x = N - bisect.bisect_left(A, f - A[p])
	if x == 0:
		continue
	ans += A[p] * x + R[-x]
	count += x
ans -= (count - M) * f
print(ans)


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 check(x):
	Y = np.searchsorted(A, x - A)
	return N * N - Y.sum() <= M
ok = 10 ** 6
ng = 0
while abs(ng - ok) > 1:
	mid = (ok + ng) // 2
	if check(mid):
		ok = mid
	else:
		ng = mid
Acum = np.zeros(N + 1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, ok - A)
answer = (Acum[-1] - Acum[Y]).sum() + (A * (N - Y)).sum()
answer += ng * (M - (N - Y).sum())
print(answer)


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)


(N, M) = map(int, input().split())
a = [2 * 10 ** 5 + 1] + sorted(map(int, input().split()), reverse=True)

def solve(x):
	count = 0
	j = N
	for i in range(1, N + 1):
		while a[i] + a[j] < x:
			j -= 1
		count += j
	return count
(left, right) = (0, 2 * 10 ** 5 + 1)
while left < right - 1:
	mid = (left + right) // 2
	if solve(mid) >= M:
		left = mid
	else:
		right = mid
acc = a[:]
acc[0] = 0
for i in range(N):
	acc[i + 1] += acc[i]
ans = 0
j = N
for i in range(1, N + 1):
	while a[i] + a[j] < left + 1:
		j -= 1
	ans += a[i] * j + acc[j]
	M -= j
if M:
	ans += left * M
print(ans)


def count(pre, a, x):
	cnt = 0
	val = 0
	for i in reversed(range(n)):
		if 2 * a[i] < x:
			break
		(lo, hi) = (0, n - 1)
		while lo < hi:
			mid = (lo + hi) // 2
			if a[mid] + a[i] < x:
				lo = mid + 1
			else:
				hi = mid
		cnt += 1 + 2 * (i - lo)
		val += 2 * (i - lo + 1) * a[i] + (pre[i] - pre[lo]) * 2
	return (cnt, val)
(n, m) = map(int, input().split())
a = list(sorted(map(int, input().split())))
pre = [0]
for i in range(n):
	pre.append(a[i] + pre[-1])
(lo, hi) = (0, 2 * a[-1])
while lo < hi:
	mid = (lo + hi + 1) // 2
	(cnt, _) = count(pre, a, mid)
	if cnt < m:
		hi = mid - 1
	else:
		lo = mid
(cnt, val) = count(pre, a, lo)
print(val - (cnt - m) * lo)


8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from bisect import bisect_left
from itertools import accumulate
(N, M) = map(int, input().split())
A = sorted(list(map(int, input().split())))
A_r = list(reversed(A))
B = [0] + list(accumulate(A_r))

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_r:
	idx = bisect_left(A, MIN - Ai)
	ans += Ai * (N - idx) + B[N - idx]
	count += N - idx
print(ans - (count - M) * MIN)


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)


import sys
import bisect
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def hantei(t):
	global n, m, a
	ret = 0
	for sa in a:
		ret += n - bisect.bisect_left(a, t - sa)
	if ret <= m:
		return True
	else:
		return False

def nibun(l, r):
	if r == l:
		return l
	f = (l + r) // 2
	if hantei(f):
		return nibun(l, f)
	else:
		return nibun(f + 1, r)
p = nibun(0, 3 * 10 ** 5)
a.reverse()
na = []
sna = 0
for sa in a:
	sna += sa
	na.append(sna)
na.reverse()
na.append(0)
a.reverse()
res = 0
f = 0
for sa in a:
	q = bisect.bisect_left(a, p - sa)
	f += n - q
	res += na[q] + sa * (n - q)
res += (p - 1) * (m - f)
print(res)


import sys, bisect
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	b[i] = a[i] + b[i + 1]
ok = 0
ng = 200001
while ng - ok > 1:
	mid = (ok + ng) // 2
	cnt = 0
	for e in a:
		k = bisect.bisect_left(a, mid - e)
		cnt += n - k
	if cnt >= m:
		ok = mid
	else:
		ng = mid
c = 0
res = 0
for e in a:
	k = bisect.bisect_left(a, ok + 1 - e)
	res += b[k] + e * (n - k)
	c += n - k
res += ok * (m - c)
print(res)


import sys
readline = sys.stdin.readline
(N, M) = list(map(int, readline().split()))
A = sorted(list(map(int, readline().split())))
sumA = [0] + A.copy()
for i in range(1, len(sumA)):
	sumA[i] += sumA[i - 1]
ok = -1
ng = 10 ** 5 * 2 + 1
import bisect

def isOk(x):
	cnt = 0
	for left in A:
		right = x - left
		ind = bisect.bisect_left(A, right)
		cnt += N - ind
	if cnt > M:
		return True
	else:
		return False
while abs(ng - ok) > 1:
	mid = abs(ng + ok) // 2
	if isOk(mid):
		ok = mid
	else:
		ng = mid
ans = 0
num = 0
for left in A:
	right = ok - left
	ind = bisect.bisect_left(A, right)
	ans += sumA[-1] - sumA[ind] + (N - ind) * left
	num += N - ind
if num > M:
	ans -= (num - M) * ok
print(ans)


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)


from bisect import bisect as B
LI = lambda : map(int, input().split())
A = 0
(n, m) = LI()
a = sorted(LI())
R = a[::-1]

def Q(x, M):
	w = 0
	for i in range(n):
		y = x - R[i]
		c = B(a, y - 1)
		w += n - c
		if w >= M:
			return 1
	return 0
N = a[-1] * 3
O = -1
while N - O > 1:
	f = (O + N) // 2
	if Q(f, m):
		O = f
	else:
		N = f
P = 0
for i in range(n):
	e = n - B(a, O - a[i] - 1)
	P += e
	A += e * a[i] * 2
print(A - O * (P - m))


import bisect
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = [0] * N
B[-1] = A[-1]
for i in range(N - 2, -1, -1):
	B[i] = B[i + 1] + A[i]

def C(mid):
	tmp = 0
	for a in A:
		pos = bisect.bisect_right(A, mid - a)
		tmp += N - pos
	return tmp > M
lb = 0
rb = 10 ** 6
while rb - lb > 1:
	happy = (lb + rb) // 2
	if C(happy):
		lb = happy
	else:
		rb = happy
ans = 0
cnt = 0
for a in A:
	pos = bisect.bisect_right(A, rb - a)
	if pos == N:
		continue
	ans += B[pos] + (N - pos) * a
	cnt += N - pos
ans += (M - cnt) * rb
print(ans)


from bisect import bisect_left
from itertools import accumulate
(n, m) = map(int, input().split())
hands = [int(x) for x in input().split()]
increasing = sorted(hands)
hands = list(reversed(increasing))
xs = [0] + list(accumulate(hands))
max_x = 2 * 10 ** 5 + 1
min_x = 0

def canGet(x):
	count = 0
	for hand in increasing:
		idx = bisect_left(increasing, x - hand)
		count += n - idx
	return count >= m
while max_x - min_x > 1:
	mid = (max_x + min_x) // 2
	if canGet(mid):
		min_x = mid
	else:
		max_x = mid
ans = 0
count = 0
for Ai in hands:
	idx = bisect_left(increasing, min_x - Ai)
	ans += Ai * (n - idx) + xs[n - idx]
	count += n - idx
print(ans - (count - m) * min_x)


import bisect

def is_ok(a, target, m):
	num = 0
	for val in a:
		index = bisect.bisect_left(a, target - val)
		num += len(a) - index
	if num <= m:
		return True
	else:
		return False
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
(ok, ng) = (10 ** 10, -1)
while ok - ng > 1:
	mid = (ok + ng) // 2
	if is_ok(a, mid, m):
		ok = mid
	else:
		ng = mid
rui = [0] * (n + 1)
for i in range(n):
	rui[i + 1] = rui[i] + a[i]
cnt = 0
ret = 0
for val in a:
	index = bisect.bisect_left(a, ok - val)
	num = len(a) - index
	cnt += num
	ret += num * val + (rui[-1] - rui[index])
ret += (m - cnt) * ng
print(ret)


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)


import sys
import numpy as np
(N, M) = list(map(int, sys.stdin.readline().rstrip().split()))
A = np.array(sys.stdin.readline().rstrip().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 1 < right - left:
	x = (left + right) // 2
	if shake_cnt(x) >= M:
		left = x
	else:
		right = x
X = np.searchsorted(A, right - A)
shake = N * N - X.sum()
Acum = np.zeros(N + 1, np.int64)
Acum[1:] = np.cumsum(A)
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()
happy += (M - shake) * left
print(happy)


from bisect import bisect_left
(N, M) = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
l = 0
r = 2 * 10 ** 5 + 5
while l + 1 < r:
	mid = (l + r) // 2
	m = 0
	for a in A:
		idx = bisect_left(A, mid - a)
		m += N - idx
	if m >= M:
		l = mid
	else:
		r = mid
s = [0] * (N + 1)
for i in range(N):
	s[i + 1] = s[i] + A[i]
ans = 0
m = 0
for a in A:
	idx = bisect_left(A, l - a)
	m += N - idx
	ans += s[N] - s[idx]
	ans += a * (N - idx)
ans -= (m - M) * l
print(ans)


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

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

def __starting_point():
	main()
__starting_point()


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

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

def happiness(x):
	c = 0
	i = 0
	ci = 0
	for j in reversed(range(len(A))):
		while i < n and A[j] + A[i] >= x:
			ci += A[i]
			i += 1
		c += ci + A[j] * i
	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)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] *= -1
a.sort()
from bisect import bisect_left, bisect_right

def check(mid):
	mm = 0
	for i in range(n):
		if -(a[i] + a[0]) < mid:
			break
		mm += bisect_right(a, -(mid + a[i]))
	return mm
ok = 0
ng = 10 ** 10 + 7
while ng != ok + 1:
	mid = (ok + ng) // 2
	if check(mid) >= m:
		ok = mid
	else:
		ng = mid
b = [0]
for i in a:
	b.append(b[-1] + i)
ans = 0
for i in range(n):
	if -(a[i] + a[0]) < ok:
		break
	ind = bisect_right(a, -(ok + a[i]))
	ans += a[i] * ind
	ans += b[ind]
print(-(ans + (check(ok) - m) * ok))


from itertools import accumulate
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0] * (2 * a[0] + 1)
for i in range(n):
	b[a[i]] += 1
b = list(accumulate(b[::-1]))[::-1]
s = list(accumulate([0] + a))
ok = 0
ng = 2 * a[0] + 1
while ng - ok > 1:
	mid = (ng + ok) // 2
	cnt = 0
	for i in range(n):
		cnt += b[max(0, mid - a[i])]
	if cnt >= m:
		ok = mid
	else:
		ng = mid
cnt = 0
ans = 0
for i in range(n):
	t = min(b[max(0, ng - a[i])], m - cnt)
	ans += s[t] + a[i] * t
	cnt += t
ans += (m - cnt) * ok
print(ans)


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


def main():
	import bisect
	import numpy as np
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l1 = np.array(l)

	def bise(x):
		y = np.searchsorted(l1, x - l1)
		return n * n - y.sum()
	left = -1
	right = l[-1] * 2 + 1
	while right > left + 1:
		mid = (right + left) // 2
		if bise(mid) >= k:
			left = mid
		else:
			right = mid
	ans = 0
	count = 0
	acc = [0]
	for i in l:
		acc.append(acc[-1] + i)
	for i in l:
		index = bisect.bisect_left(l, right - i)
		ans += i * (n - index) + acc[n] - acc[index]
		count += n - index
	print(ans - (count - k) * left)

def __starting_point():
	main()
__starting_point()


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)


import bisect
from itertools import accumulate

def func(x):
	cnt = 0
	for i in a:
		index = bisect.bisect_left(a, x - i)
		cnt += N - index
	if cnt >= M:
		return True
	else:
		return False
(N, M) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ar = sorted(a, reverse=True)
b = [0] + list(accumulate(ar))
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
cnt = 0
for i in ar:
	index = bisect.bisect_left(a, MIN - i)
	ans += i * (N - index) + b[N - index]
	cnt += N - index
print(ans - (cnt - M) * MIN)


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)


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)


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)


from bisect import bisect_right as br
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] *= -1
a.sort()
b = [0]
for i in a:
	b.append(b[-1] + i)
ng = 2 * 10 ** 5 + 7
ok = -1
while ok + 1 != ng:
	mid = (ng + ok) // 2
	co = 0
	for i in a:
		co += br(a, -(mid + i))
	if co < m:
		ng = mid
	else:
		ok = mid
ans = 0
co = 0
for i in a:
	ind = br(a, -(ok + i) - 1)
	co += ind
	ans += -b[ind] - i * ind
ans += (m - co) * ok
print(ans)


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


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
l = [n for i in range(a[0] + 1)]
for i in range(2, n + 1):
	for j in range(a[-i], a[-i + 1], -1):
		l[j] = n - i + 1
start = 2 * a[-1]
stop = 2 * a[0]
while start < stop:
	i = (start + stop + 1) // 2
	num = 0
	for j in a:
		if i - j < 0:
			num += n
		elif i - j <= a[0]:
			num += l[i - j]
		else:
			break
	if num >= m:
		start = i
	else:
		stop = i - 1
num = 0
for i in a:
	if start - i < 0:
		num += n
	elif 0 <= start - i <= a[0]:
		num += l[start - i]
	else:
		break
ans = 0
for i in a:
	if start - i < 0:
		ans += 2 * i * n
	elif start - i <= a[0]:
		ans += 2 * i * l[start - i]
	else:
		break
ans -= (num - m) * start
print(ans)


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


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)


from bisect import bisect_left
from itertools import accumulate
(N, M) = map(int, input().split())
A = sorted(list(map(int, input().split())))
A_r = list(reversed(A))
B = [0] + list(accumulate(A_r))

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_r:
	idx = bisect_left(A, MIN - Ai)
	ans += Ai * (N - idx) + B[N - idx]
	count += N - idx
print(ans - (count - M) * MIN)


(N, M, *A) = map(int, open(0).read().split())

def func(X):
	cnt = 0
	j = N
	for i in range(1, N + 1):
		while A[i] + A[j] < X:
			j -= 1
		cnt += j
	return cnt
A = [10 ** 11] + sorted(A, reverse=True)
lb = 0
ub = 10 ** 11
while ub - lb > 1:
	mid = (lb + ub) // 2
	if func(mid) >= M:
		lb = mid
	else:
		ub = mid
acc = A[:]
acc[0] = 0
for i in range(N):
	acc[i + 1] += acc[i]
ans = 0
j = N
for i in range(1, N + 1):
	while A[i] + A[j] < lb + 1:
		j -= 1
	ans += A[i] * j + acc[j]
	M -= j
if M:
	ans += lb * M
print(ans)


import numpy as np
from numpy.fft import rfft, irfft
import sys
sys.setrecursionlimit(10 ** 9)

def mi():
	return map(int, input().split())

def ii():
	return int(input())

def isp():
	return input().split()

def deb(text):
	print('-------\n{}\n-------'.format(text))
INF = 10 ** 20

class Counter:

	def __init__(self):
		self.dict = {}

	def add(self, x):
		if x in self.dict:
			self.dict[x] += 1
		else:
			self.dict[x] = 1

	def decrement(self, x):
		self.dict[x] -= 1
		if self.dict[x] <= 0:
			del self.dict[x]

	def get_dict(self):
		return self.dict

def fft(A, B, fft_len=2 * 10 ** 5):
	x = irfft(rfft(A, fft_len) * rfft(B, fft_len)) + 0.5
	return x.astype(int)

def main():
	(N, M) = mi()
	A = list(mi())
	counter = Counter()
	for a in A:
		counter.add(a)
	count_map = counter.get_dict()
	F = [0] * 2 * 10 ** 5
	for (a, count) in count_map.items():
		F[a] = count
	G = fft(F, F, fft_len=1 << 18)
	ans = 0
	handshake = M
	for x in range(len(G) - 1, 1, -1):
		if G[x] <= 0:
			continue
		count = G[x]
		if count > handshake:
			ans += handshake * x
		else:
			ans += count * x
		handshake = max(handshake - count, 0)
		if handshake == 0:
			break
	print(ans)

def __starting_point():
	main()
__starting_point()


import numpy as np
from numpy.fft import rfft, irfft
import sys
sys.setrecursionlimit(10 ** 9)

def mi():
	return list(map(int, input().split()))

def ii():
	return int(input())

def isp():
	return input().split()

def deb(text):
	print('-------\n{}\n-------'.format(text))
INF = 10 ** 20

class Polynomial:

	def __init__(self, dim=0, const=1):
		self.values = [(dim, const)]

	def __add__(self, other):
		return self.values + other.values

class PolySolver:

	def __init__(self, size, init_val=1):
		self.size = size
		self.f = np.zeros(size, np.int64)
		self.f[0] = init_val

	def multiple(self, polynomial, MOD):
		new_F = np.zeros(self.size, np.int64)
		for (dim, const) in polynomial:
			if dim != 0:
				g = np.zeros(self.size, np.int64)
				g[dim:] += self.f[:-dim]
			else:
				g = const * self.f.copy()
			new_F += g
		self.f = new_F

	def add(self, polynomial):
		for (dim, const) in polynomial:
			self.f[dim] += const

	def get_coefficient(self, dim):
		return self.f[dim]

	def fft(self, A, B, fft_len=1 << 18):
		x = irfft(rfft(A, fft_len) * rfft(B, fft_len))
		return np.rint(x).astype(np.int64)

	def convolve(self, g):
		h = self.fft(self.f, g)[:len(self.f) + len(g) - 1]
		self.f = h

def main():
	(N, M) = mi()
	A = list(mi())
	mx = 2 * 10 ** 5 + 10
	F = PolySolver(mx, init_val=0)
	for a in A:
		F.add(Polynomial(dim=a).values)
	g = F.f
	F.convolve(g)
	ans = 0
	handshake = M
	for x in range(mx - 1, 1, -1):
		count = F.get_coefficient(x)
		if count <= 0:
			continue
		if count > handshake:
			ans += handshake * x
		else:
			ans += count * x
		handshake = max(handshake - count, 0)
		if handshake == 0:
			break
	print(ans)

def __starting_point():
	main()
__starting_point()


import bisect
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
left = a[0] * 2
right = a[-1] * 2 + 1
mid = (left + right) // 2
while right - left > 1:
	mid = (left + right) // 2
	count = 0
	for i in range(n):
		j = bisect.bisect_left(a, mid - a[i])
		count += n - j
	if count >= m:
		left = mid
	else:
		right = mid
acum = [0] * (n + 1)
for i in range(n):
	acum[i + 1] = acum[i] + a[i]
ans = 0
count = 0
for i in range(n):
	j = bisect.bisect_left(a, left - a[i])
	ans += acum[n] - acum[j] + a[i] * (n - j)
	count += n - j
ans -= left * (count - m)
print(ans)


from bisect import bisect_left, bisect_right
from itertools import accumulate

def ge_m(x, m, n):
	total = 0
	for v in a:
		delta = x - v
		idx = bisect_left(a, delta)
		total += n - idx
	return total >= m
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cum = [0] + list(accumulate(a))
l = 0
r = a[-1] * 2 + 1
while r - l > 1:
	mid = (l + r) // 2
	if ge_m(mid, m, n):
		l = mid
	else:
		r = mid
num = 0
ans = 0
for v in a:
	idx = bisect_right(a, l - v)
	num += n - idx
	ans += v * (n - idx) + (cum[-1] - cum[idx])
ans += l * (m - num)
print(ans)


import bisect
import copy
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
asum = [0]
tmp = 0
for i in range(n):
	tmp += a[i]
	asum.append(tmp)
lb = 1
ub = 2 * 10 ** 5 + 1
while ub - lb > 1:
	cx = (ub + lb) // 2
	cnt = 0
	total = 0
	for ca in a:
		cy = cx - ca
		ci = bisect.bisect_left(a, cy)
		cnt += n - ci
		total += asum[n] - asum[ci] + (n - ci) * ca
	if cnt >= m:
		lb = cx
		ans = copy.deepcopy(total) - (cnt - m) * cx
	else:
		ub = cx
print(ans)


import bisect
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
S = [0] * (n + 1)
for i in range(n):
	S[i + 1] = S[i] + A[i]

def cnt(x, A, S):
	res = 0
	for (i, a) in enumerate(A):
		res += bisect.bisect_left(A, x - a)
	return res

def ans(x, A, S):
	res = 0
	for (i, a) in enumerate(A):
		res += a * bisect.bisect_left(A, x - a) + S[bisect.bisect_left(A, x - a)]
	return res
top = A[-1] * 2 + 1
bottom = 0
while top - bottom > 1:
	mid = (top + bottom) // 2
	if n * n - cnt(mid, A, S) > m:
		bottom = mid
	else:
		top = mid
print(S[-1] * 2 * n - ans(top, A, S) + bottom * (m - (n * n - cnt(top, A, S))))


import numpy as np
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
na = np.zeros(2 ** 18)
for i in a:
	na[i] += 1
fa = np.fft.fft(na)
c = np.round(np.fft.ifft(fa * fa)).astype(int)
ans = 0
cm = 0
for i in range(2 ** 18 - 1, 1, -1):
	cm += c[i]
	ans += i * c[i]
	if cm > m:
		ans -= i * (cm - m)
	if cm >= m:
		break
print(ans)


import bisect

def justM(x, N):
	sum_ = 0
	for i in range(N):
		b = bisect.bisect_left(A, x - A[i])
		sum_ += N - b
	return sum_
(N, M) = map(int, input().split())
A = sorted(map(int, input().split()))
(left, right) = (-1, 10 ** 5 * 2 + 1)
while right - left > 1:
	mid = (right + left) // 2
	s = justM(mid, N)
	if s < M:
		right = mid
	else:
		left = mid
D = left
r = [0] * (N + 1)
ans = 0
for i in range(N):
	r[i + 1] = r[i] + A[i]
cnt = 0
for i in range(N):
	b = bisect.bisect_left(A, D - A[i])
	ans += A[i] * (N - b) + (r[N] - r[b])
	cnt += N - b
print(ans - D * (cnt - M))


import sys
import numpy as np
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))

def convolve(f, g):
	fft_len = 1
	while 2 * fft_len < len(f) + len(g) - 1:
		fft_len *= 2
	fft_len *= 2
	Ff = np.fft.rfft(f, fft_len)
	Fg = np.fft.rfft(g, fft_len)
	Fh = Ff * Fg
	h = np.fft.irfft(Fh, fft_len)
	h = np.rint(h).astype(np.int64)
	return h
(N, M) = inl()
A = inl()
power = np.zeros(10 ** 5 + 1, dtype=np.int64)
for i in range(N):
	power[A[i]] += 1
P = convolve(power, power)
r = M
ans = 0
for k in range(len(P) - 1, -1, -1):
	c = min(P[k], r)
	ans += k * c
	r -= c
	if r <= 0:
		break
print(ans)


from bisect import bisect_left
(N, M) = [int(i) for i in input().split()]
n = sorted([int(x) for x in input().split()])
s = [0] * (N + 1)
s[0] = n[0]
for i in range(1, N + 1):
	s[i] = s[i - 1] + n[i - 1]
MM = n[-1] * 2
mm = n[0] * 2
while True:
	c = 0
	r = (mm + MM) // 2
	for i in range(N):
		c += N - bisect_left(n, r - n[i])
	if MM - mm < 2:
		break
	elif c >= M:
		mm = r
	elif c < M:
		MM = r
v = 0
for i in range(N):
	j = bisect_left(n, r - n[i])
	v += s[N] - s[j] + (N - j) * n[i]
v = v - (c - M) * r
print(v)


def main():
	import numpy as np
	(n, m) = list(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)

def __starting_point():
	main()
__starting_point()


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


from bisect import bisect_left
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def doesOver(k):
	cnt = 0
	for a in A:
		cnt += N - bisect_left(A, k - a)
	return cnt >= M
overEq = 0
less = A[-1] * 2 + 100
while less - overEq > 1:
	mid = (less + overEq) // 2
	if doesOver(mid):
		overEq = mid
	else:
		less = mid
accA = [0] * (N + 1)
for i in range(1, N + 1):
	accA[i] = accA[i - 1] + A[i - 1]
ans = 0
cnt = 0
for a in A:
	left = bisect_left(A, overEq - a)
	ans += accA[N] - accA[left]
	ans += (N - left) * a
	cnt += N - left
ans -= (cnt - M) * overEq
print(ans)


import bisect
import copy

def check(a, b, bar):
	sm = 0
	cnt = 0
	n = len(a)
	for x in a:
		i = bisect.bisect_left(a, bar - x)
		if i == n:
			continue
		cnt += n - i
		sm += b[i] + x * (n - i)
	return (cnt, sm)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = copy.deepcopy(a)
for (i, _) in enumerate(b[:-1]):
	b[n - i - 2] += b[n - i - 1]
left = 0
right = b[0] * 2
while right - left > 1:
	middle = (right + left) // 2
	if check(a, b, middle)[0] < m:
		right = middle
	else:
		left = middle
print(check(a, b, left)[1] - left * (check(a, b, left)[0] - m))


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
MAX_VAL = 10 ** 5 + 1
hand = [0] * MAX_VAL
for a in A:
	hand[a] += 1
import numpy as np

def convolve(f, g):
	fft_len = 1
	while 2 * fft_len < len(f) + len(g) - 1:
		fft_len *= 2
	fft_len *= 2
	Ff = np.fft.rfft(f, fft_len)
	Fg = np.fft.rfft(g, fft_len)
	Fh = Ff * Fg
	h = np.fft.irfft(Fh, fft_len)
	h = np.rint(h).astype(np.int64)
	return h[:len(f) + len(g) - 1]
right_hand = np.array(hand, dtype=int)
left_hand = np.array(hand, dtype=int)
H = convolve(left_hand, right_hand)
ans = 0
for i in range(len(H) - 1, -1, -1):
	if H[i] == 0:
		continue
	if H[i] <= M:
		ans += i * H[i]
		M -= H[i]
	else:
		ans += M * i
		break
print(ans)


from bisect import bisect_right
(N, M) = map(int, input().split())
(*A,) = map(int, input().split())
INF = 10 ** 12
A.sort()
ac = [0] * (N + 1)
for i in range(1, N + 1):
	ac[i] = ac[i - 1] + A[i - 1]

def f(x):
	v = 0
	for i in A:
		v += N - bisect_right(A, x - i)
	return v

def g(l):
	ans = INF
	for i in A:
		res = bisect_right(A, l - i)
		if 0 <= res < N:
			ans = min(ans, A[res] + i)
	return ans
(l, r) = (0, INF + 1)
while r - l > 1:
	m = (l + r) // 2
	if f(m) >= M:
		l = m
	else:
		r = m
ans = 0
for i in A:
	v1 = N - bisect_right(A, r - i)
	ans += ac[N] - ac[N - v1] + v1 * i
ans += (M - f(r)) * g(l)
print(ans)


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)


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


import sys
import math
import fractions
from collections import defaultdict
import bisect
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : list(map(int, stdin.readline().split()))
nl = lambda : list(map(int, stdin.readline().split()))
(N, M) = nm()
A = nl()
A.sort()
S = [0]
S[0] = A[0]
for i in range(1, N):
	S.append(S[i - 1] + A[i])

def clc_shake(x):
	tot = 0
	for i in range(N):
		th = x - A[i]
		inds = bisect.bisect_left(A, th)
		tot += N - inds
	return tot
l = 0
r = 2 * 10 ** 6
c = 0
while l + 1 < r:
	c = (l + r) // 2
	if clc_shake(c) < M:
		r = c
	else:
		l = c
ans = 0
for i in range(N):
	th = r - A[i]
	inds = bisect.bisect_left(A, th)
	if inds != 0:
		ans += (N - inds) * A[i] + (S[N - 1] - S[inds - 1])
	else:
		ans += (N - inds) * A[i] + S[N - 1]
M2 = M - clc_shake(r)
ans += M2 * l
print(ans)


def ints():
	return [int(x) for x in input().split()]

def ii():
	return int(input())
(N, M) = ints()
A = ints()
A.sort()
A.reverse()

def combinations_and_kofukudo(x):
	c = 0
	k = 0
	si = 0
	i = 0
	for j in reversed(range(N)):
		while i < N and A[i] + A[j] >= x:
			si += A[i]
			i += 1
		c += i
		k += si + A[j] * i
	return (c, k)

def bsearch(l, u):
	m = (l + u) // 2
	(c, k) = combinations_and_kofukudo(m)
	if c < M:
		return bsearch(l, m)
	else:
		if l == m:
			print(k - (c - M) * l)
			exit()
		return bsearch(m, u)
bsearch(0, A[0] * 2 + 1)


import bisect
import itertools
import numpy as np

def search_cut(N, M, A):
	high_cut = A[-1] * 2
	low_cut = A[0] * 2
	while high_cut > low_cut + 1:
		mid = (high_cut + low_cut) // 2
		count = (N - np.searchsorted(A, mid - A, side='left')).sum()
		if count > M:
			low_cut = mid
		else:
			high_cut = mid
	return (low_cut, high_cut)

def happiness(N, M, A, low_cut, high_cut):
	A_sum = np.zeros(N + 1)
	A_sum[1:] = np.cumsum(A)
	X = np.searchsorted(A, high_cut - A, side='left')
	happiness = (A_sum[-1] - A_sum[X]).sum()
	happiness += ((N - X) * A).sum()
	happiness += (M - (N - X).sum()) * low_cut
	return int(happiness)
(N, M) = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
A = np.sort(A)
(low_cut, high_cut) = search_cut(N, M, A)
ans = happiness(N, M, A, low_cut, high_cut)
print(ans)


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

def count_bigger_x(x):
	cnt = 0
	piv = N - 1
	for a in A:
		while piv >= 0 and a + A[piv] >= x:
			piv -= 1
		cnt += N - piv - 1
	return cnt

def is_ok(x):
	cnt = count_bigger_x(x)
	return cnt >= M

def bisect(ng, ok):
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if is_ok(mid):
			ok = mid
		else:
			ng = mid
	return ok
x = bisect(2 * A[-1] + 1, 2 * A[0] - 1)
ans = 0
piv = N - 1
for a in A:
	while piv >= 0 and a + A[piv] >= x:
		piv -= 1
	ans += (N - piv - 1) * a
ans *= 2
ans -= 1 * x * (count_bigger_x(x) - M)
print(ans)


def ints():
	return [int(x) for x in input().split()]

def ii():
	return int(input())
(N, M) = ints()
A = ints()
A.sort()

def combinations(x):
	s = 0
	i = 0
	j = N - 1
	while j >= 0:
		while i < N and A[i] + A[j] < x:
			i += 1
		s += N - i
		j -= 1
	return s

def koufukudo(x):
	s = 0
	si = 0
	j = 0
	i = N - 1
	while j < N:
		while i >= 0 and A[i] + A[j] >= x:
			si += A[i]
			i -= 1
		s += si + A[j] * (N - 1 - i)
		j += 1
	return s

def bsearch(lower, upper):
	l = lower
	u = upper
	m = (l + u) // 2
	c = combinations(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[-1] * 2 + 1)
print(koufukudo(x) - dm * x)


from bisect import bisect_left

def solve(m):
	r = N - 1
	l = 0
	cnt = 0
	while 0 <= r and l < N:
		if A[r] + A[l] < m:
			l += 1
		else:
			cnt += N - l
			r -= 1
	return cnt
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
S = [0] * (N + 1)
for i in range(N):
	S[i + 1] = S[i] + A[i]
ok = 0
ng = 10 ** 21
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	cnt = solve(mid)
	if cnt >= M:
		ok = mid
	else:
		ng = mid
X = ok
amari = float('inf')
cnt = 0
score = 0
for (i, Ai) in enumerate(A):
	Aj = X - Ai
	j = bisect_left(A, Aj)
	score += S[N] - S[j] + Ai * (N - j)
	cnt += N - j
	if j < N:
		amari = min(amari, A[i] + A[j])
print(score - (cnt - M) * amari)


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


(N, M) = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
bi = [0] * (A[0] + 1)
for a in A:
	bi[a] += 1
cum = [0] * (A[0] + 1)
for i in range(1, A[0] + 1):
	cum[i] = cum[i - 1] + bi[i]
cum_max = cum[-1]
left = 0
right = A[0] * 2 + 1
while right - 1 != left:
	x = (right + left) // 2
	num = 0
	for a in A:
		b = max(x - a, 1)
		if b <= A[0]:
			num += cum_max - cum[b - 1]
	if num >= M:
		left = x
	else:
		right = x
ans = 0
cum_A = [0] * (N + 1)
for i in range(1, N + 1):
	cum_A[i] = cum_A[i - 1] + A[i - 1]
for a in A:
	b = max(right - a, 1)
	if b > A[0]:
		break
	c = cum_max - cum[b - 1]
	M -= c
	ans += a * c + cum_A[c]
ans += M * left
print(ans)


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


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

def combinations(x):
	s = 0
	i = 0
	for j in reversed(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(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)
	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)


import sys

def f(x):
	p = 0
	cnt = 0
	for i in range(n - 1, -1, -1):
		while p < n and a[i] + a[p] < x:
			p += 1
		cnt += n - p
	return cnt
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
(l, r) = (a[0] * 2, a[n - 1] * 2)
while True:
	if r - l <= 1:
		if f(r) == m:
			md = r
			break
		else:
			md = l
			break
	md = (r + l) // 2
	k = f(md)
	if k == m:
		break
	elif k > m:
		l = md
	else:
		r = md
p = 0
cnt = 0
ans = 0
for q in range(n - 1, -1, -1):
	while p < n and a[q] + a[p] <= md:
		p += 1
	if p == n:
		break
	cnt += n - p
	ans += a[q] * (n - p) * 2
ans += (m - cnt) * md
print(ans)


from bisect import bisect_left as bisect
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def combination(X):
	res = 0
	for i in range(N):
		j = bisect(A, X - A[i])
		res += N - j
	return res
l = 0
r = 2 * 10 ** 5 + 1
m = (l + r) // 2
for i in range(20):
	c = combination(m)
	if c < M:
		r = m
	else:
		l = m
	m = (l + r) // 2
if combination(m) >= M:
	m += 1
S = [0] * (N + 1)
for i in range(N):
	S[i] = S[i - 1] + A[i]
ans = 0
for i in range(N):
	j = bisect(A, m - A[i])
	ans += A[i] * (N - j)
	ans += S[N - 1] - S[j - 1]
ans += (M - combination(m)) * (m - 1)
print(ans)


import numpy as np
import sys
input = sys.stdin.readline

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

def __starting_point():
	main()
__starting_point()


from bisect import *
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
left = 0
right = 200001
while right - left > 1:
	mid = left + (right - left) // 2
	count = 0
	for i in range(n - 1, -1, -1):
		count += n - bisect_left(a, mid - a[i])
		if count >= m:
			break
	if m <= count:
		left = mid
	else:
		right = mid
ans = 0
a_accum = [0]
for i in range(n):
	a_accum.append(a_accum[i] + a[-1 - i])
for i in range(n - 1, -1, -1):
	count = n - bisect_left(a, left - a[i])
	ans += a_accum[count] + a[i] * count
	m -= count
ans += left * m
print(ans)


import numpy as np
(n, m) = list(map(int, input().split()))
A = np.array(input().split(), np.int64)
A = np.sort(A)

def is_ok(x):
	cnt = n ** 2 - np.searchsorted(A, x - A, side='left').sum()
	if cnt >= m:
		return True
	else:
		return False
l = 0
r = 2 * 10 ** 5 + 1
while l + 1 < r:
	c = (l + r) // 2
	if is_ok(c):
		l = c
	else:
		r = c
from itertools import accumulate
B = [0] + list(A)
B = list(accumulate(B))
ans = 0
cnt = 0
for a in A:
	j = np.searchsorted(A, l - a, side='left').sum()
	cnt += n - j
	ans += B[-1] - B[j] + a * (n - j)
ans -= (cnt - m) * l
print(ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = [0 for i in range(10 ** 5 + 1)]
S = [0]
s = 0
for i in range(N):
	B[A[i]] += 1
	s += A[i]
	S.append(s)
for i in range(2, 10 ** 5 + 2):
	B[-i] += B[-i + 1]
d = 0
u = 2 * 10 ** 5
for i in range(30):
	x = (u + d) // 2
	if i == 28:
		x += 1
	m = 0
	for i in range(N):
		a = A[i]
		y = max(x - a, 0)
		if y <= 10 ** 5:
			m += B[y]
	if m >= M:
		d = x
	else:
		u = x
ans = 0
for i in range(N):
	a = A[i]
	x = max(d - a, 0)
	if x <= 10 ** 5:
		y = B[x]
	else:
		y = 0
	ans += S[N] - S[N - y] + a * y
ans -= (m - M) * d
print(ans)


from bisect import bisect_left

def main():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	(L, R) = (0, 2 * 10 ** 5 + 1)
	while L + 1 < R:
		P = (L + R) // 2
		cnt = 0
		for v in a:
			x = P - v
			cnt += n - bisect_left(a, x)
		if cnt >= m:
			L = P
		else:
			R = P
	csum = [0]
	for v in a:
		csum.append(v)
	for i in range(n):
		csum[i + 1] += csum[i]
	ans = 0
	cnt = 0
	for v in a:
		x = L - v
		idx = bisect_left(a, x)
		cnt += n - idx
		ans += csum[-1] - csum[idx]
		ans += v * (n - idx)
	ans -= (cnt - m) * L
	print(ans)
main()


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)


from bisect import bisect_left

def check(x):
	cnt = 0
	l = n
	r = n
	for i in range(n):
		while True:
			if l == 0:
				break
			if a[l - 1] < x - a[i]:
				break
			l -= 1
		cnt += r - l
	return cnt >= m
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ok = 0
ng = 2 * 10 ** 5 + 10
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if check(mid):
		ok = mid
	else:
		ng = mid
ru = [0] * (n + 1)
for i in range(n):
	ru[i + 1] = ru[i] + a[i]
ans = 0
cnt = 0
r = n
ok = ok + 1
for i in range(n):
	l = bisect_left(a, ok - a[i])
	cnt += r - l
	ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)


import sys
import bisect
input = sys.stdin.readline

def main():
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	(l, r) = (-1, 10 ** 6)
	while r - l > 1:
		k = (r + l) // 2
		count = 0
		for i in range(n):
			count += n - bisect.bisect_left(a, k - a[i])
		if count > m:
			l = k
		else:
			r = k
	ans = 0
	count = 0
	b = [0] * (n + 1)
	for i in range(n):
		b[i + 1] += b[i] + a[i]
	for i in range(n):
		index = bisect.bisect_left(a, r - a[i])
		ans += b[n] - b[index] + a[i] * (n - index)
		count += n - index
	if count < m:
		ans += (m - count) * l
	print(ans)

def __starting_point():
	main()
__starting_point()


import bisect
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
INF = 10 ** 9
A.append(INF)
(left, right) = (0, 2 * max(A))
while left + 1 < right:
	mid = left + right >> 1
	cnt = sum((N - bisect.bisect_left(A, mid - A[i]) for i in range(N)))
	if cnt >= M:
		left = mid
	else:
		right = mid
acc = [0]
for i in range(N):
	acc.append(acc[-1] + A[i])
ans = 0
cnt = 0
for i in range(N):
	idx = bisect.bisect_left(A, left - A[i])
	cnt += N - idx
	ans += (N - idx) * A[i] + acc[N] - acc[idx]
ans -= (cnt - M) * left
print(ans)


import sys
sys.setrecursionlimit(10000000)
from bisect import *
INF = 500000
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
(l, r) = (0, 10 ** 6)
while l + 1 < r:
	m = (l + r) // 2
	cnt = 0
	for a in A:
		cnt += N - bisect_left(A, m - a)
	if cnt < M:
		r = m
	else:
		l = m
f = [0] + A[::-1]
for i in range(N):
	f[i + 1] += f[i]
(cnt, ans) = (0, 0)
for a in A:
	i = bisect_right(A, l - a)
	ans += f[N - i] + (N - i) * a
	cnt += N - i
print(ans + (M - cnt) * l)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
import bisect

def func(x):
	C = 0
	for p in l:
		q = x - p
		j = bisect.bisect_left(l, q)
		C += n - j
	if C >= m:
		return True
	else:
		return False
l_ = 0
r_ = 2 * 10 ** 5 + 1
while l_ + 1 < r_:
	c_ = (l_ + r_) // 2
	if func(c_):
		l_ = c_
	else:
		r_ = c_
ans = 0
cnt = 0
lr = sorted(l, reverse=True)
from itertools import accumulate
cum = [0] + list(accumulate(lr))
for i in lr:
	j = bisect.bisect_left(l, l_ - i)
	ans += i * (n - j) + cum[n - j]
	cnt += n - j
ans -= (cnt - m) * l_
print(ans)


import numpy as np

def convolve(A, B):
	dtype = np.int64
	(fft, ifft) = (np.fft.rfft, np.fft.irfft)
	(a, b) = (len(A), len(B))
	if a == b == 1:
		return np.array([A[0] * B[0]])
	n = a + b - 1
	k = 1 << (n - 1).bit_length()
	AB = np.zeros((2, k), dtype=dtype)
	AB[0, :a] = A
	AB[1, :b] = B
	return np.rint(ifft(fft(AB[0]) * fft(AB[1]))).astype(np.int64)[:n]
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = np.zeros(100001)
for i in a:
	cnt[i] += 1
c = convolve(cnt, cnt)
ans = 0
for i in range(len(c))[::-1]:
	if c[i] > 0:
		p = min(m, c[i])
		m -= p
		ans += i * p
		if m == 0:
			break
print(ans)


from bisect import bisect_left
from itertools import accumulate

def resolve():

	def getCount(x):
		cnt = 0
		for a in A:
			idx = bisect_left(A, x - a)
			cnt += N - idx
		return cnt >= M
	(N, M) = list(map(int, input().split()))
	A = sorted(map(int, input().split()))
	ng = 10 ** 9
	ok = 0
	while ng - ok > 1:
		mid = (ok + ng) // 2
		if getCount(mid):
			ok = mid
		else:
			ng = mid
	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)

def __starting_point():
	resolve()
__starting_point()


import numpy as np
(n, k) = list(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)


import numpy as np
(N, M, *A) = list(map(int, open(0).read().split()))
A = np.sort(A)
B = np.cumsum(np.concatenate([[0], A[::-1]]))
l = -1
r = 10 ** 6
while l + 1 < r:
	s = (l + r) // 2
	cnt = np.sum(N - np.searchsorted(A, s - A))
	if cnt >= M:
		l = s
	else:
		r = s
ind = np.searchsorted(A, r - A)
M -= np.sum(N - ind)
ans = np.sum(B[N - ind] + A * (N - ind)) + M * l
print(ans)


from bisect import bisect_left
(N, M) = list(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)


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)


(n, m) = 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)


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)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
from bisect import bisect_left

def isok(n):
	sum = 0
	for i in range(N):
		sum += N - bisect_left(A, n - A[i])
	return sum >= M
(start, end) = (0, 2 * 10 ** 5 + 1)
while end - start > 1:
	mid = (start + end) // 2
	if isok(mid):
		start = mid
	else:
		end = mid
b = [A[0]]
for i in range(1, N):
	b.append(b[-1] + A[i])
l = 0
ans = 0
bn = b[N - 1]
for i in range(N):
	a = bisect_left(A, start - A[i])
	l += N - a
	if a > 0:
		ans += A[i] * (N - a) + bn - b[a - 1]
	else:
		ans += A[i] * (N - a) + bn
ans -= start * (l - M)
print(ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = [0] * (N + 1)
for i in range(1, N + 1):
	B[i] = B[i - 1] + A[i - 1]
D = [0] * (2 * 10 ** 5 + 1)
for i in range(N):
	D[A[i]] += 1
for i in range(len(D) - 1, 0, -1):
	D[i - 1] += D[i]
l = -1
r = 2 * 10 ** 5 + 1
while r - l > 1:
	m = (l + r) // 2
	s = 0
	for i in range(N):
		s += D[max(1, m - A[i])]
	if s >= M:
		l = m
	else:
		r = m
ans = 0
s = 0
for i in range(N):
	v = max(0, r - A[i])
	t = max(0, min(D[v], M - s))
	ans += B[t] + t * A[i]
	s += t
ans += l * (M - s)
print(ans)


(N, M) = map(int, input().split())
A = sorted([int(a) for a in input().split()])
C = [0] * 101010
S = [0] * 101010
for a in A[::-1]:
	C[a] += 1
	S[a] += a
for i in range(101000)[::-1]:
	C[i] += C[i + 1]
	S[i] += S[i + 1]

def cnt(n):
	re = 0
	for a in A:
		b = min(max(n - a, 0), 101000)
		re += C[b]
	return re

def calc(n):
	re = 0
	for a in A:
		b = min(max(n - a, 0), 101000)
		re += S[b] + C[b] * a
	return re
(l, r) = (0, 200001)
while r - l > 1:
	m = (l + r) // 2
	if cnt(m) >= M:
		l = m
	else:
		r = m
print(calc(l) - (cnt(l) - M) * l)


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

def __starting_point():
	main()
__starting_point()


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)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
b = [0]
for i in reversed(a):
	b.append(b[-1] + i)

def search(i):
	if a[-1] < i:
		return 0
	mi = 0
	ma = n - 1
	while mi != ma:
		m = (mi + ma) // 2
		if a[m] >= i:
			ma = m
		else:
			mi = m + 1
	return n - mi

def countmax(i):
	ans = 0
	for j in a:
		ans += search(i - j)
	return ans
mi = 0
ma = a[-1] * 2
while mi != ma:
	md = (mi + ma) // 2 + 1
	if countmax(md) > m:
		mi = md
	else:
		ma = md - 1
ans = 0
for j in a:
	i = search(mi + 1 - j)
	ans += b[i] + i * j
ans += (m - countmax(mi + 1)) * mi
print(ans)


from itertools import accumulate
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
MAX = 10 ** 5
scores = [0] * (2 * MAX + 1)
for e in a:
	scores[e] += 1
acc = list(accumulate(scores))

def f(x):
	cnt = 0
	for e in a:
		cnt += n - acc[max(0, x - e - 1)]
	return cnt
l = 0
r = 2 * MAX + 1
while r - l > 1:
	mid = (l + r) // 2
	if f(mid) >= m:
		l = mid
	else:
		r = mid
scores_sum = [i * e for (i, e) in enumerate(scores)]
acc_sum = list(accumulate(scores_sum))
sm = sum(a)
ans = 0
cnt_sum = 0
for e in a:
	i = max(0, l - e - 1)
	cnt = n - acc[i]
	ans += e * cnt + sm - acc_sum[i]
	cnt_sum += cnt
ans -= (cnt_sum - m) * l
print(ans)


(n, m) = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
s = sum(A)
SA = [0]
for a in A:
	SA.append(SA[-1] + a)
for i in range(n + 1):
	SA[i] = s - SA[i]
(l, r) = (0, 2 * max(A) + 1)
import bisect

def chk(x):
	ct = 0
	for a in A:
		ct += n - bisect.bisect_left(A, max(x - a, 0))
	if ct >= m:
		return True
	else:
		return False

def count(x):
	ct = 0
	for a in A:
		ct += n - bisect.bisect_left(A, max(x - a, 0))
	return ct
while r - l > 1:
	mid = (l + r) // 2
	if chk(mid):
		l = mid
	else:
		r = mid
ans = 0
for a in A:
	aa = bisect.bisect_left(A, max(l - a, 0))
	ans += SA[aa] + a * (n - aa)
print(ans - l * (count(l) - m))


from bisect import bisect_left, bisect_right
from itertools import accumulate
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

def isOK(x):
	num = 0
	for (k, a) in enumerate(A, start=1):
		i = bisect_left(A, x - a)
		num += n - i
	return num >= m
l = 0
r = 2 * 10 ** 5 + 1
while l + 1 < r:
	mid = (l + r) // 2
	if isOK(mid):
		l = mid
	else:
		r = mid
s = 0
num = 0
acc = list(accumulate([0] + A))
for a in A:
	i = bisect_right(A, l - a)
	s += a * (n - i) + acc[n] - acc[i]
	num += n - i
ans = s + l * (m - num)
print(ans)


from itertools import accumulate
import bisect
(N, M) = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
OK = 0
NG = max(A) * 2 + 1
c = 0
while NG - OK > 1:
	mid = (OK + NG) // 2
	cnt = 0
	for a in A:
		cnt += N - bisect.bisect_left(A, mid - a)
	if cnt >= M:
		OK = mid
	else:
		NG = mid
S = list(accumulate(A))
ans = 0
c = 0
for a in A:
	idx = bisect.bisect_right(A, OK - a)
	if idx >= 1:
		ans += a * (N - idx) + S[-1] - S[idx - 1]
	else:
		ans += a * (N - idx) + S[-1]
	c += N - idx
ans += OK * (M - c)
print(ans)


import numpy as np
from numpy.fft import rfft, irfft
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
a = np.zeros(10 ** 5 + 1)
for i in range(N):
	a[A[i]] += 1
b = rfft(a, 2 * 10 ** 5 + 1)
b = irfft(b * b, 2 * 10 ** 5 + 1)
b = np.rint(b).astype(np.int64)
c = 0
ans = 0
for n in range(2 * 10 ** 5, 1, -1):
	if c + b[n] < M:
		c += b[n]
		ans += b[n] * n
	else:
		ans += (M - c) * n
		c = M
		break
print(ans)


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)


from itertools import accumulate
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
	d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))
left = 0
right = A[0] * 2 + 1
while right - left > 1:
	mid = (left + right) // 2
	m = 0
	for i in range(N):
		m += d[max(0, mid - A[i])]
	if m >= M:
		left = mid
	else:
		right = mid
ans = 0
m = 0
for i in range(N):
	t = min(d[max(0, right - A[i])], M - m)
	ans += S[t] + A[i] * t
	m += t
ans += left * (M - m)
print(ans)


from bisect import bisect_left
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
left = 0
right = max(A) * 2 + 1
while left + 1 < right:
	mid = (left + right) // 2
	cnt = 0
	for i in range(N):
		cnt += N - bisect_left(A, mid - A[i])
	if cnt >= M:
		left = mid
	else:
		right = mid
mon = [0]
for a in A:
	mon.append(mon[-1] + a)
ans = 0
cnt = 0
for i in range(N):
	bi = bisect_left(A, left - A[i])
	ans += mon[-1] - mon[bi] + (N - bi) * A[i]
	cnt += N - bi
ans -= (cnt - M) * left
print(ans)


import numpy as np
from numpy.fft import rfft, irfft
import sys
sys.setrecursionlimit(10 ** 9)

def mi():
	return list(map(int, input().split()))

def ii():
	return int(input())

def isp():
	return input().split()

def deb(text):
	print('-------\n{}\n-------'.format(text))
INF = 10 ** 20

class Polynomial:

	def __init__(self, coefficient=None, dim=0, const=1):
		if coefficient == None:
			self.coefficient = np.zeros(dim + 1, np.int64)
			self.coefficient[dim] = const
		else:
			self.coefficient = coefficient

	def __add__(self, other):
		(f, g) = (self.coefficient, other.coefficient)
		if len(f) > len(g):
			(f, g) = (g, f)
		h = Polynomial(dim=len(g) - 1, const=0)
		h.coefficient[len(f):] += g[len(f):]
		h.coefficient[:len(f)] += f + g[:len(f)]
		return h

	def __iadd__(self, other):
		h = self.__add__(other)
		self.coefficient = h.coefficient
		return self

	def __mul__(self, other):
		f = self.coefficient
		g = other.coefficient
		h = Polynomial()
		h.coefficient = self.fft(f, g)[:len(f) + len(g) - 1]
		return h

	def __len__(self):
		return len(self.coefficient)

	def __getitem__(self, key):
		return self.coefficient[key]

	def get_coefficient(self, x):
		return self.coefficient[x]

	def fft(self, A, B, fft_len=1 << 18):
		x = irfft(rfft(A, fft_len) * rfft(B, fft_len))
		return np.rint(x).astype(np.int64)

def main():
	(N, M) = mi()
	A = list(mi())
	coefficient = [0] * (2 * 10 ** 5 + 10)
	for a in A:
		coefficient[a] += 1
	f = Polynomial(coefficient=coefficient)
	g = f * f
	ans = 0
	handshake = M
	for x in range(len(g) - 1, 1, -1):
		count = g[x]
		if count <= 0:
			continue
		if count > handshake:
			ans += handshake * x
		else:
			ans += count * x
		handshake = max(handshake - count, 0)
		if handshake == 0:
			break
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if n == 1:
	print(a[0] * 2)
	exit()
from bisect import bisect_left, bisect_right

def f(x):
	global n, a
	ret = 0
	for i in range(n):
		ret += n - bisect_left(a, x - a[i])
	return ret
(l, r) = (-1, 10 ** 6)
while l + 1 < r:
	k = l + (r - l) // 2
	if f(k) >= m:
		l = k
	else:
		r = k
(co, ans) = (0, 0)
for i in range(n):
	co += n - bisect_right(a, l - a[i])
	ans += (n - bisect_right(a, l - a[i])) * a[i]
print(2 * ans + (m - co) * l)


(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
a_rev = a[::-1]
(ok, ng) = (1, 200001)
while ng - ok > 1:
	x = (ok + ng) // 2
	num = 0
	cur = 0
	for i in range(n - 1, -1, -1):
		while cur < n and a[i] + a[cur] >= x:
			cur += 1
		num += cur
	if num < m:
		ng = x
	else:
		ok = x
just = ok
ans = 0
larger_cnt = 0
cur = 0
a_cum = [0]
for i in range(n):
	a_cum.append(a_cum[-1] + a[i])
for i in range(n):
	while cur < n and a[i] + a_rev[cur] <= just:
		cur += 1
	larger_cnt += n - cur
	ans += (n - cur) * a[i] + a_cum[n - cur]
ans += just * (m - larger_cnt)
print(ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
U = A[0] * 2
cgs = [0] * (U + 1)
for a in A:
	cgs[a] += 1
for i in range(U, 0, -1):
	cgs[i - 1] += cgs[i]

def is_ok(n):
	m = 0
	for a in A:
		m += cgs[max(n - a, 0)]
	return m >= M
ok = A[-1] * 2
ng = U + 1
while ng - ok > 1:
	m = (ok + ng) // 2
	if is_ok(m):
		ok = m
	else:
		ng = m
cps = A[:]
for i in range(1, N):
	cps[i] += cps[i - 1]
result = 0
for a in A:
	t = cgs[max(ok - a, 0)]
	if t != 0:
		result += a * t + cps[t - 1]
		M -= t
result += ok * M
print(result)


from itertools import accumulate
from operator import mul
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * (10 ** 5 * 2 + 1)
for a in A:
	B[a] += 1
C = list(accumulate(B[::-1]))[::-1]
(l, r) = (1, 10 ** 5 * 2 + 1)
while r - l > 1:
	m = l + (r - l + 1) // 2
	if sum((C[max(0, m - a)] for a in A)) >= M:
		l = m
	else:
		r = m
D = list(accumulate(map(mul, range(10 ** 5 * 2, -1, -1), B[::-1])))[::-1]
ans = sum((D[max(0, l - a)] - (l - a) * C[max(0, l - a)] for a in A)) + l * M
print(ans)


from bisect import bisect_left as BL
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

def isok(border):
	res = 0
	for i in range(N):
		res += N - BL(A, border - A[i])
	return res >= M
ok = 0
ng = A[-1] * 2 + 1
mid = (ok + ng) // 2
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if isok(mid):
		ok = mid
	else:
		ng = mid
B = reversed(A)
SB = [0]
for b in B:
	SB.append(b + SB[-1])
ans = 0
shake_c = 0
for i in range(N):
	goodshake = N - BL(A, ok - A[i])
	shake_c += goodshake
	ans += A[i] * goodshake
	ans += SB[goodshake]
ans -= (shake_c - M) * ok
print(ans)


import sys
from bisect import bisect_right, bisect_left
from itertools import accumulate
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():

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

	def is_ok(x):
		cnt = 0
		for a in A:
			t = x - a
			idx = bisect_right(A, t)
			cnt += n - idx
		return cnt < m
	(n, m) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort()
	(ng, ok) = (0, 10 ** 15 + 1)
	mth = meguru_bisect(ok, ng)
	R = [0] + list(accumulate(A))
	res = 0
	cnt = 0
	for a in A:
		s = mth - a
		left = bisect_left(A, s)
		res += (n - left) * a + R[-1] - R[left]
		cnt += n - left
	print(res - mth * (cnt - m))

def __starting_point():
	resolve()
__starting_point()


from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
	(N, M) = list(map(int, input().split()))
	As = list(map(int, input().split()))
	As.sort()

	def isOK(x):
		num = 0
		for (k, A) in enumerate(As, start=1):
			i = bisect_left(As, x - A)
			num += N - i
			if num >= M:
				return True
			elif num + (N - k) * N < M:
				return False
		return num >= M
	(ng, ok) = (2 * 10 ** 5 + 1, 0)
	while abs(ok - ng) > 1:
		mid = (ng + ok) // 2
		if isOK(mid):
			ok = mid
		else:
			ng = mid
	score = 0
	num = 0
	accAs = list(accumulate([0] + As))
	for A in As:
		i = bisect_right(As, ok - A)
		score += A * (N - i) + accAs[N] - accAs[i]
		num += N - i
	ans = score + ok * (M - num)
	print(ans)
solve()


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


import numpy as np
(N, M) = list(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)


(n, m) = map(int, input().split())
a = sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
	num = 0
	for ax in a:
		bi = bisect.bisect_left(a, now - ax)
		num += bi
	return n ** 2 - num
mi = a[0] * 2 - 1
ma = a[-1] * 2 + 1
kotae = ma
while mi < ma:
	now = (mi + ma) // 2
	which = hantei(now) <= m
	if which:
		ma = now
		kotae = now
	else:
		mi = now + 1
kotae -= 1
suma = [0] * (n + 1)
suma[-2] = a[-1]
for i in range(n - 2, -1, -1):
	suma[i] = suma[i + 1] + a[i]
ans = 0
kazu = 0
for ax in a:
	bi = bisect.bisect_left(a, kotae - ax)
	ans += (n - bi) * ax + suma[bi]
	kazu += n - bi
print(ans - (kazu - m) * kotae)


from itertools import accumulate
from bisect import bisect_left, bisect_right
(N, M) = list(map(int, input().split()))
(*A,) = list(map(int, input().split()))
A.sort()
acc = list(accumulate(A[::-1]))[::-1] + [0]

def isok(x):
	cnt = 0
	for a in A:
		cnt += N - bisect_left(A, x - a)
	return cnt >= M
l = 0
r = 202020
while l + 1 < r:
	m = (l + r) // 2
	if isok(m):
		l = m
	else:
		r = m
ans = 0
cnt = 0
for a in A:
	i = bisect_left(A, l - a)
	ans += a * (N - i) + acc[i]
	cnt += N - i
if cnt > M:
	ans -= l * (cnt - M)
print(ans)


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


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)


from bisect import bisect_left
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

def get_count(tot):
	ret = 0
	for i in range(N):
		cnt = bisect_left(A, tot - A[i])
		ret += N - cnt
	return ret
Asum = A[:]
for i in range(N - 2, -1, -1):
	Asum[i] += Asum[i + 1]

def get_sum(tot):
	ret = 0
	for i in range(N):
		idx = bisect_left(A, tot - A[i])
		cnt = N - idx
		ret += A[i] * cnt
		if idx == N:
			continue
		ret += Asum[idx]
	return ret
ok = 0
ng = 10 ** 12
while ok + 1 != ng:
	md = (ok + ng) // 2
	if M <= get_count(md):
		ok = md
	else:
		ng = md
ans = get_sum(ok + 1) + (M - get_count(ok + 1)) * ok
print(ans)


import bisect
(N, M) = list(map(int, input().split()))
data = list(map(int, input().split()))
data.sort()

def cost(x):
	re = 0
	for i in range(N):
		idx = bisect.bisect_left(data, x - data[i])
		re += N - idx
	return re
lb = 0
ub = 2 * max(data) + 1
while ub - lb > 1:
	mid = (ub + lb) // 2
	if cost(mid) >= M:
		lb = mid
	else:
		ub = mid
ans = 0 - (cost(lb) - M) * lb
cum_data = [0] * (N + 1)
for i in range(1, N + 1):
	cum_data[i] = cum_data[i - 1] + data[i - 1]
data_idx = [0] * N
for i in range(N):
	idx = bisect.bisect_left(data, lb - data[i])
	data_idx[i] = idx
for i in range(N):
	ans += (N - data_idx[i]) * data[i]
	ans += cum_data[N] - cum_data[data_idx[i]]
print(ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
sumA = [0]
for i in range(N):
	sumA.append(sumA[-1] + A[i])
import bisect

def num_shakes(border):
	ret = 0
	for i in range(N):
		if A[i] + A[-1] < border:
			continue
		rest = border - A[i]
		j = bisect.bisect_left(A, rest)
		ret += N - j
	return ret
(l, r) = (A[0] * 2, A[-1] * 2 + 1)
while r - l > 1:
	p = (l + r) // 2
	if num_shakes(p) >= M:
		l = p
	else:
		r = p
m = num_shakes(r)
ans = l * (M - m)
for i in range(N):
	if A[i] + A[-1] < r:
		continue
	rest = r - A[i]
	j = bisect.bisect_left(A, rest)
	ans += A[i] * (N - j) + (sumA[-1] - sumA[j])
print(ans)


from bisect import bisect_left, bisect_right
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a_cs = [0] * (n + 1)
for i in range(n):
	a_cs[i + 1] = a_cs[i] + a[n - 1 - i]

def check(x):
	cnt = 0
	for ai in a:
		idx = bisect_left(a, x - ai)
		cnt += n - idx
	return cnt >= m
lb = 1
ub = 2 * 10 ** 5 + 5
while ub - lb > 1:
	mid = (ub + lb) // 2
	if check(mid):
		lb = mid
	else:
		ub = mid
ans = 0
cnt = 0
for ai in a:
	idx = bisect_left(a, lb - ai)
	ans += ai * (n - idx) + a_cs[n - idx]
	cnt += n - idx
ans -= lb * (cnt - m)
print(ans)


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)

def __starting_point():
	resolve()
__starting_point()


from itertools import accumulate
from bisect import bisect_left

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

	def count(k):
		cnt = 0
		for a in A:
			cnt += bisect_left(A, k - a)
		return cnt
	ok = 0
	ng = 10 ** 10 + 1
	while ng - ok > 1:
		mid = (ok + ng) // 2
		if count(mid) < n ** 2 - m:
			ok = mid
		else:
			ng = mid
	border = ok
	k = n ** 2 - count(border)
	Acc = [0] + list(accumulate(A))
	s = Acc[-1]
	ans = 0
	for a in A:
		idx = bisect_left(A, border - a)
		ans += a * (n - idx) + (s - Acc[idx])
	ans -= border * (k - m)
	print(ans)
main()


k = 34
K = 1 << k
nu = lambda L: int(''.join([bin(K + a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + '0'
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i + 1) * k - 1:-i * k - 1] for i in range(len(B) * 2 - 1)]]
(N, M) = map(int, input().split())
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
	B[a] += 1
C = li(st(nu(B) ** 2))
ans = 0
for i in range(200001)[::-1]:
	a = min(M, C[i])
	M -= a
	ans += a * i
print(ans)


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


ii = lambda : int(input())
mi = lambda : list(map(int, input().split()))
li = lambda : list(map(int, input().split()))
(n, m) = mi()
alis = li()
alis.sort()
ok = 0
ng = alis[n - 1] * 2 + 1
from bisect import bisect_left as bl
while ng - ok > 1:
	mid = (ok + ng) // 2
	ima = 0
	for i in range(n):
		ima += n - bl(alis, mid - alis[i])
	if ima >= m:
		ok = mid
		outrange = ima - m
	else:
		ng = mid
acu_alis = [0] * n
ima = 0
for i in range(n):
	acu_alis[i] = alis[i] + ima
	ima = alis[i] + ima
ans = 0
for i in range(n):
	tmp = bl(alis, ok - alis[i])
	if tmp == 0:
		ans += n * alis[i] + acu_alis[n - 1]
	else:
		ans += (n - tmp) * alis[i] + acu_alis[n - 1] - acu_alis[tmp - 1]
ans -= outrange * ok
print(ans)


import bisect
from itertools import accumulate
(N, M) = map(int, input().split())
A = sorted(list(map(int, input().split())))
ans = 0
xOK = A[0] * 2
xNG = A[-1] * 2 + 1
nx = 0
while xOK + 1 < xNG:
	x = (xOK + xNG) // 2
	nx = 0
	for a in A:
		nx += N - bisect.bisect_left(A, x - a)
		if nx >= M:
			xOK = x
			break
	else:
		xNG = x
S = [0] + list(accumulate(A))
ans = 0
nnx = 0
for a in A:
	nx = bisect.bisect_right(A, xOK - a)
	ans += a * (N - nx) + (S[N] - S[nx])
	nnx += N - nx
ans += xOK * (M - nnx)
print(ans)


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

def PairCount_and_TotalSum_over(x):
	(c, k, si, i) = [0, 0, 0, 0]
	for j in reversed(range(N)):
		while i < N and A[i] + A[j] >= x:
			si += A[i]
			i += 1
		c += i
		k += si + A[j] * i
	return (c, k)

def binary_search(l, u):
	m = (l + u) // 2
	(c, k) = PairCount_and_TotalSum_over(m)
	if c < M:
		return binary_search(l, m)
	elif l == m:
		print(k - (c - M) * l)
	else:
		return binary_search(m, u)
binary_search(0, A[0] * 2 + 1)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
import bisect

def count(k):
	cnt = 0
	for i in range(n):
		cnt += n - bisect.bisect_left(a, k - a[i])
	return cnt
l = 0
r = 2 * 10 ** 5 + 10
while r - l > 1:
	med = (r + l) // 2
	if count(med) < m:
		r = med
	elif count(med) >= m:
		l = med
ans = 0
dp = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	dp[i] = dp[i - 1] + a[-i]
for i in range(n):
	x = a[i]
	index = n - bisect.bisect_left(a, l - x)
	ans += dp[index] + x * index
print(ans - l * (count(l) - m))


import bisect as bi

def S(T):
	global N
	res = 0
	for i in range(N):
		res += k(i, T)
	return res

def k(i, T):
	global A
	N = len(A)
	res = N - bi.bisect_left(A, T - A[i])
	return res
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
l = A[0] * 2
r = A[N - 1] * 2
while r - l > 1:
	m = (l + r) // 2
	if S(m) >= M:
		l = m
	else:
		r = m
b = [0]
for i in range(N):
	b.append(b[-1] + A[N - 1 - i])
ans = 0
cnt = 0
for i in range(N):
	cnt += k(i, l)
	ans += A[i] * k(i, l) + b[k(i, l)]
if cnt > M:
	ans -= l * (cnt - M)
print(ans)


import numpy as np
from numpy.fft import rfft, irfft
(N, M) = list(map(int, input().split()))
(*A,) = list(map(int, input().split()))
B = np.zeros(5 * 10 ** 5)
for a in A:
	B[a] += 1
L = 5 * 10 ** 5
FB = rfft(B, L)
C = np.rint(irfft(FB * FB)).astype(int)
ans = 0
for i in range(2 * 10 ** 5, -1, -1):
	c = C[i]
	if not c:
		continue
	if M - c > 0:
		ans += i * c
		M -= c
	else:
		ans += i * M
		break
print(ans)


from bisect import bisect_left
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

def count(x):
	ret = 0
	for a in A:
		ret += N - bisect_left(A, x - a)
	return ret
overEq = 0
less = 10 ** 7
while less - overEq > 1:
	mid = (less + overEq) // 2
	if count(mid) >= M:
		overEq = mid
	else:
		less = mid
ans = 0
cnt = [0] * N
for a in A:
	i = N - bisect_left(A, overEq - a)
	ans += i * a
	if i > 0:
		cnt[-i] += 1
for i in range(1, N):
	cnt[i] += cnt[i - 1]
for (a, c) in zip(A, cnt):
	ans += a * c
ans -= overEq * (count(overEq) - M)
print(ans)


import sys, collections as cl, bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10 ** 9 + 7
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return list(map(int, input().split()))

def onem():
	return int(input())

def s(x):
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x) - 1):
		if aa != x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a

def jo(x):
	return ' '.join(map(str, x))

def max2(x):
	return max(list(map(max, x)))

def In(x, a):
	k = bs.bisect_left(a, x)
	if k != len(a) and a[k] == x:
		return True
	else:
		return False

def pow_k(x, n):
	ans = 1
	while n:
		if n % 2:
			ans *= x
		x *= x
		n >>= 1
	return ans
(N, M) = m()
a = l()
a.sort()
aaa = s(a)
po = [0 for i in range(10 ** 5 + 1)]
ans = 0
for i in range(N):
	po[a[i]] += 1
for i in range(10 ** 5 - 1, -1, -1):
	po[i] += po[i + 1]
ll = 0
rr = 10 ** 5 * 2
while True:
	mid = (ll + rr) // 2
	if mid == ll:
		co = 0
		for i in range(N):
			ui = a[i]
			if mid > ui + 10 ** 5:
				continue
			elif ui >= mid:
				co += N
			else:
				co += po[mid - ui]
		cco = 0
		mid = rr
		for i in range(N):
			ui = a[i]
			if mid > ui + 10 ** 5:
				continue
			elif ui >= mid:
				cco += N
			else:
				cco += po[mid - ui]
		if co == cco:
			mid = rr
		elif cco == M:
			mid = rr
			co = cco
		else:
			mid = ll
		break
	co = 0
	for i in range(N):
		ui = a[i]
		if mid > ui + 10 ** 5:
			continue
		elif ui >= mid:
			co += N
		else:
			co += po[mid - ui]
	if co < M:
		rr = mid
	else:
		ll = mid
a.sort(reverse=True)
dp = [0]
ans -= mid * (co - M)
for i in range(N):
	dp.append(dp[-1] + a[i])
for i in range(N):
	pl = a[i]
	if pl >= mid:
		ans += pl * N + dp[-1]
	elif pl + 10 ** 5 < mid:
		continue
	else:
		ans += pl * po[mid - pl] + dp[po[mid - pl]]
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
l = 0
r = 3 * 10 ** 5
while r - l > 1:
	m = (r + l) // 2
	ind = N - 1
	cnt = 0
	for a in A:
		while ind >= 0 and A[ind] + a < m:
			ind -= 1
		cnt += ind + 1
	if cnt >= M:
		l = m
	else:
		r = m
B = [0]
for a in A:
	B.append(B[-1] + a)
ans = 0
border = l
ind = N - 1
cnt = 0
for a in A:
	while ind >= 0 and A[ind] + a < border:
		ind -= 1
	cnt += ind + 1
	ans += a * (ind + 1) + B[ind + 1]
ans -= (cnt - M) * border
print(ans)


def main():
	import bisect
	import numpy as np
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l = np.array(l)

	def bise(x):
		y = np.searchsorted(l, x - l)
		return n * n - y.sum()
	left = -1
	right = l[-1] * 2 + 1
	while right > left + 1:
		mid = (right + left) // 2
		if bise(mid) >= k:
			left = mid
		else:
			right = mid
	ans = 0
	acc = np.zeros(n + 1, np.int64)
	acc[1:] = l.cumsum()
	x = np.searchsorted(l, right - l)
	count = n * n - x.sum()
	ans = (acc[-1] - acc[x]).sum() + (l * (n - x)).sum()
	print(ans - (count - k) * left)

def __starting_point():
	main()
__starting_point()


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

def calc(x):
	(count, sum) = (0, 0)
	(j, t) = (0, 0)
	for i in reversed(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)

def binary_search(x, y):
	mid = (x + y) // 2
	(count, sum) = calc(mid)
	if count < M:
		return binary_search(x, mid)
	elif x == mid:
		print(sum - (count - M) * mid)
	else:
		return binary_search(mid, y)
binary_search(0, A[0] * 2 + 1)


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)


from itertools import accumulate
MAX = 2 * 10 ** 5 + 5
(N, M, *A) = map(int, open(0).read().split())
B = [0] * MAX
for a in A:
	B[a] += 1
C = list(accumulate(reversed(B)))[::-1]
(ng, ok) = (1, MAX)
while abs(ok - ng) > 1:
	m = (ok + ng) // 2
	if sum((C[max(0, m - a)] for a in A)) >= M:
		ng = m
	else:
		ok = m
D = list(accumulate(reversed(list((i * b for (i, b) in enumerate(B))))))[::-1]
print(sum((D[max(0, ng - a)] - (ng - a) * C[max(0, ng - a)] for a in A)) + ng * M)


import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r
from itertools import accumulate
(n, m, *a) = map(int, sys.stdin.read().split())
a.sort()

def count(border):
	res = 0
	for x in a:
		b = border - x
		res += n - bi_l(a, b)
	return res

def main():
	(lo, hi) = (1, a[-1] * 2 + 1)
	while lo + 1 < hi:
		border = (lo + hi) // 2
		if count(border) >= m:
			lo = border
		else:
			hi = border
	s = a.copy() + [0]
	(*s,) = accumulate(s[::-1])
	tot = 0
	for x in a:
		b = lo - x
		c = n - bi_l(a, b)
		tot += x * c + s[c]
	tot -= lo * (count(lo) - m)
	print(tot)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = [0]
for ai in a:
	s.append(ai + s[-1])

def count(x, accum=False):
	ret = 0
	for ai in a:
		(lo, hi) = (-1, n)
		while hi - lo > 1:
			mid = (lo + hi) // 2
			if ai + a[mid] >= x:
				lo = mid
			else:
				hi = mid
		ret += ai * hi + s[hi] if accum else hi
	return ret
(lo, hi) = (0, 1000000000)
while hi - lo > 1:
	mid = (lo + hi) // 2
	if count(mid) >= m:
		lo = mid
	else:
		hi = mid
print(count(lo, accum=True) - (count(lo) - m) * lo)


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


import sys
input = sys.stdin.readline

def main():
	(n, m) = list(map(int, input().split()))
	a = sorted(list(map(int, input().split())))
	import bisect
	(l, r) = (0, a[-1] * 2 + 1)
	while r - l > 1:
		x = (l + r) // 2
		cnt = 0
		for ai in a:
			cnt += n - bisect.bisect_left(a, x - ai)
		if cnt >= m:
			l = x
		else:
			r = x
	x = (l + r) // 2
	ans = 0
	cnt = 0
	a_ = 0
	cs_a = [0]
	for ai in a:
		a_ += ai
		cs_a.append(a_)
	for ai in a:
		bi = bisect.bisect_right(a, x - ai)
		cnt += n - bi
		ans += cs_a[-1] - cs_a[bi] + (n - bi) * ai
	print(ans + (m - cnt) * x)

def __starting_point():
	main()
__starting_point()


from bisect import bisect_left
(n, m) = map(int, input().split())
import math
import numpy as np
import decimal
import collections
import itertools
import sys

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	p = find(x)
	q = find(y)
	if p == q:
		return None
	if p > q:
		(p, q) = (q, p)
	par[p] += par[q]
	par[q] = p

def same(x, y):
	return find(x) == find(y)

def size(x):
	return -par[find(x)]
par = [-1 for i in range(n)]

def prime_numbers(x):
	if x < 2:
		return []
	prime_numbers = [i for i in range(x)]
	prime_numbers[1] = 0
	for prime_number in prime_numbers:
		if prime_number > math.sqrt(x):
			break
		if prime_number == 0:
			continue
		for composite_number in range(2 * prime_number, x, prime_number):
			prime_numbers[composite_number] = 0
	return [prime_number for prime_number in prime_numbers if prime_number != 0]

def is_prime(x):
	if x < 2:
		return False
	if x == 2 or x == 3 or x == 5:
		return True
	if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
		return False
	prime_number = 7
	difference = 4
	while prime_number <= math.sqrt(x):
		if x % prime_number == 0:
			return False
		prime_number += difference
		difference = 6 - difference
	return True
BIT = [0] * (n + 1)

def add(i, x):
	while i <= n:
		BIT[i] += x
		i += i & -i

def query(i):
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s
a = list(map(int, input().split()))
a.sort(reverse=True)
(l, r) = (0, 10 ** 6)
while r - l > 1:
	m2 = (l + r) // 2
	cnt = 0
	ind = n - 1
	for i in a:
		while ind >= 0 and a[ind] + i < m2:
			ind -= 1
		cnt += ind + 1
	if cnt >= m:
		l = m2
	else:
		r = m2
cum = [0]
for i in a:
	cum.append(cum[-1] + i)
ans = 0
cnt2 = 0
ind2 = n - 1
b = l
for i in a:
	while ind2 >= 0 and a[ind2] + i < b:
		ind2 -= 1
	cnt2 += ind2 + 1
	ans += (ind2 + 1) * i + cum[ind2 + 1]
print(ans - (cnt2 - m) * b)


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


def main():
	from bisect import bisect_right
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()

	def calc(x):
		tmp = 0
		for a in A:
			tmp += N - bisect_right(A, x - a - 0.5)
		return tmp
	l = 0
	r = 3 * 10 ** 5
	while r - l > 1:
		mid = (l + r) // 2
		if calc(mid) >= M:
			l = mid
		else:
			r = mid
	B = [0] * (N + 1)
	for i in range(N):
		B[i + 1] = B[i] + A[i]
	ans = 0
	for a in A:
		tmp = bisect_right(A, r - a - 0.5)
		M -= N - tmp
		ans += a * (N - tmp) + (B[-1] - B[tmp])
	ans += M * l
	print(ans)
main()


import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
	ret = 0
	for a in A:
		target = v - a
		idx = bisect.bisect_left(A, target)
		ret += n - idx
	return ret

def _sum(A, n, v, sums):
	ss = 0
	for a in A:
		target = v - a
		idx = bisect.bisect_left(A, target)
		ss += sums[n] - sums[idx]
		ss += (n - idx) * a
	return ss

def solve(N: int, M: int, A: 'List[int]'):
	A.sort()
	sums = [0]
	for a in A:
		sums.append(sums[-1] + a)
	l = -1
	r = max(A) * 2 + 1
	while r - l > 1:
		m = (r + l) // 2
		cnt = _count(A, N, m)
		if cnt >= M:
			l = m
		else:
			r = m
	cnt = _count(A, N, l)
	ret = _sum(A, N, l, sums)
	ret -= (cnt - M) * l
	print(ret)
	return ret

def solve_(N: int, M: int, A: 'List[int]'):
	A.sort(reverse=True)
	q = [(-A[0] * 2, 0, 0)]
	ret = 0
	cnt = 0
	while cnt < M:
		(s, i, j) = heapq.heappop(q)
		ret += -s
		cnt += 1
		print((i, j))
		if i == j and i < N - 1:
			heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
		else:
			if cnt < M:
				ret += -s
				cnt += 1
				print((j, i))
			heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
			if j < N - 1:
				heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
	print(ret)
	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)

def __starting_point():
	main()
__starting_point()


import numpy as np
from numpy.fft import rfft, irfft

def main():
	(n, m) = map(int, input().split())
	A = np.array(list(map(int, input().split())))
	F = np.bincount(A)
	fft_len = 2 * 10 ** 5 + 1
	Ff = rfft(F, fft_len)
	G = np.rint(irfft(Ff * Ff, fft_len)).astype(np.int64)
	G_acc = G.cumsum()
	remove_cnt = n ** 2 - m
	border = np.searchsorted(G_acc, n ** 2 - m)
	x = n ** 2 - m - G_acc[border - 1]
	remove_sum = (G[:border] * np.arange(border)).sum() + border * x
	ans = A.sum() * 2 * n - remove_sum
	print(ans)

def __starting_point():
	main()
__starting_point()


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


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


from bisect import bisect_left
from bisect import bisect_right
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = [0] * (n + 1)
for i in range(1, n + 1):
	S[i] = S[i - 1] + A[i - 1]

def solve(x):
	case = 0
	for i in range(n):
		case += n - bisect_right(A, x - A[i] - 1)
	return case
right = 2 * A[-1] + 1
left = 0
while abs(right - left) > 1:
	mid = (right + left) // 2
	if solve(mid) >= m:
		left = mid
	else:
		right = mid
Kijun = left
ans = 0
for i in range(n):
	case = n - bisect_right(A, Kijun - A[i] - 1)
	ans += case * A[i] + (S[n] - S[n - case])
ans -= (solve(Kijun) - m) * Kijun
print(ans)


from bisect import bisect_left
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = list(reversed(a))
rs = [0] * n
rs[0] = a[0]
for (i, x) in enumerate(a[1:]):
	rs[i + 1] = rs[i] + x
L = a[-1] * 2
H = a[0] * 2
while H - L > 1:
	M = (L + H) // 2
	count = 0
	for x in a:
		count += n - bisect_left(b, M - x)
	if count == m:
		L = M
		break
	elif count > m:
		L = M
	else:
		H = M
ans = 0
count = 0
for x in a:
	c = n - 1 - bisect_left(b, L - x)
	count += c + 1
	if c >= 0:
		ans += rs[c] + x * (c + 1)
print(ans - (count - m) * L)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
OK = 0
NG = max(A) * 2 + 1
import bisect
while NG - OK > 1:
	mid = (OK + NG) // 2
	score = 0
	for a in A:
		x = bisect.bisect_left(A, mid - a)
		score += N - x
		if score >= M:
			OK = mid
			break
	else:
		NG = mid
from itertools import accumulate
S = list(accumulate(A))
ANS = 0
ups = 0
for a in A:
	x = bisect.bisect_right(A, OK - a)
	if x != 0:
		ANS += (N - x) * a + (S[-1] - S[x - 1])
	else:
		ANS += (N - x) * a + S[-1]
	ups += N - x
ANS += (M - ups) * OK
print(ANS)


(N, M) = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
(nA, sA, i) = ([N, N], [0], N - 1)
for a in range(1, A[0] * 2):
	di = 0
	while i - di >= 0 and A[i - di] == a:
		di += 1
	nA.append(nA[-1] - di)
	i -= di
for a in A:
	sA.append(sA[-1] + a)
(L, R, ans) = (0, A[0] * 2 + 1, 0)
while R - L > 1:
	mid = L + (R - L) // 2
	mA = [nA[max(mid - A[i], 0)] for i in range(N)]
	sM = sum(mA)
	if M <= sM:
		L = mid
		ans = sum([A[i] * mA[i] + sA[mA[i]] for i in range(N)]) - mid * (sM - M)
	else:
		R = mid
print(ans)