module mod_fft
  implicit none
  integer, parameter :: intkind = 8, realkind = 16, cmpkind = 16
  real(realkind), parameter :: pi = acos(-1.0_realkind), dpi = 2.0_realkind * pi
contains
  function convolve(a, na, b, nb) result(res)
    integer, intent(in) :: na, nb
    integer(intkind), intent(in) :: a(0:na), b(0:nb)
    integer :: p, i
    integer(intkind) :: res(0:na + nb)
    complex(cmpkind), allocatable :: fa(:), fb(:), f(:)
    p = find_pow2(na + nb + 1)
    allocate(fa(p), fb(p), f(p))
    call init(a, na, fa, p)
    call dft(fa, p)
    call init(b, nb, fb, p)
    call dft(fb, p)
    f = fa * fb
    call dft(f, p, .true.)
    res = nint(real(f(1:na + nb + 1), realkind), intkind)
  end
  integer function find_pow2(n) result(res)
    integer, intent(in) :: n
    res = n - 1
    res = or(res, rshift(res, 1))
    res = or(res, rshift(res, 2))
    res = or(res, rshift(res, 4))
    res = or(res, rshift(res, 8))
    res = or(res, rshift(res, 16))
    res = res + 1
  end
  subroutine init(a, n, f, p)
    integer, intent(in) :: n, p
    integer(intkind), intent(in) :: a(0:n)
    complex(cmpkind), intent(out) :: f(p)
    integer :: i
    f(1:n + 1) = cmplx(real(a(0:n), realkind), 0.0_realkind, cmpkind)
    f(n + 2:p) = cmplx(0.0_realkind, 0.0_realkind, cmpkind)
  end
  subroutine dft(f, p, inverse)
    integer, intent(in) :: p
    complex(cmpkind), intent(inout) :: f(p)
    logical, optional, intent(in) :: inverse
    logical :: inv
    inv = merge(inverse, .false., present(inverse))
    call fftdft(f, p, inv)
    if (inv) f = f / real(p, realkind)
  end
  recursive subroutine fftdft(f, p, inverse)
    integer, intent(in) :: p
    complex(cmpkind), intent(inout) :: f(p)
    logical, intent(in) :: inverse
    real(realkind) :: theta
    complex(cmpkind) :: f1(p / 2), f2(p / 2), z, pz
    integer :: i
    if (p == 1) return
    f1 = f(1:p:2)
    call fftdft(f1, p / 2, inverse)
    f2 = f(2:p:2)
    call fftdft(f2, p / 2, inverse)
    theta = merge(-1.0_realkind, 1.0_realkind, inverse) * dpi / real(p, realkind)
    z = exp(cmplx(0.0_realkind, theta, cmpkind))
    pz = cmplx(1.0_realkind, 0.0_realkind, cmpkind)
    do i = 1, p / 2
      f(i) = f1(i) + pz * f2(i)
      f(i + p / 2) = f1(i) - pz * f2(i)
      pz = pz * z
    end do
  end
end module mod_fft
program handshake
  use mod_fft
  implicit none
  integer :: n, i, maxa
  integer, dimension(100000) :: a
  integer(8) :: m, cnt = 0, x = 0
  integer(intkind), dimension(0:100000) :: p = 0, q = 0
  integer(intkind), dimension(0:200000) :: c = 0
  read(*,*) n, m
  read(*,*) a(1:n)
  maxa = maxval(a(1:n))
  do i = 1, n
    p(a(i)) = p(a(i)) + 1
  end do
  q = p
  c(0:2 * maxa) = convolve(p, maxa, q, maxa)
  do i = 2 * maxa, 0, -1
    if (c(i) + cnt >= m) then
      x = x + (m - cnt) * i
      exit
    else
      x = x + c(i) * i
      cnt = cnt + c(i)
    end if
  end do
  write(*,'(i0)') x
end program handshake