n,m,*a=$<.read.split.map &:to_i

a.sort!
cs=[0]
a.map{|x|cs<<cs.last+x}
$last=[0,0,0,0]
(0..a[-1]*2).bsearch{|h|
	s=0
	q=0
	r=0
	(n-1).downto(0){|i|
		idx=a.bsearch_index{|b|a[i]+b>=h}||n
		idy=a.bsearch_index{|b|a[i]+b>h}||n
		q+=n-idy
		r+=idy-idx
		s+=cs[n]-cs[idy]+a[i]*(n-idy)
	}
	$last=[h,s,q,r]
	q+r<=m
}
h,s,q,r=$last
p s+(m-q)*h