module mod_ntt
  implicit none
  integer, parameter :: intkind = 16
  integer(intkind), parameter :: modu = 7881299347898369_intkind, root = 3_intkind
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(intkind), allocatable :: fa(:), fb(:), f(:)
    integer(intkind) :: res(0:na + nb)
    integer :: p
    p = find_pow2(na + nb + 1)
    allocate(fa(0:p - 1), fb(0:p - 1), f(0:p - 1))
    call init(a, na, fa, p)
    call ntt(fa, p)
    call init(b, nb, fb, p)
    call ntt(fb, p)
    f = mod(fa * fb, modu)
    call ntt(f, p, .true.)
    res = f(0:na + nb)
  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)
    integer(intkind), intent(out) :: f(0:p - 1)
    f(0:n) = a(0:n)
    f(n + 1:p - 1) = 0
  end
  subroutine ntt(f, p, invert)
    integer, intent(in) :: p
    integer(intkind), intent(inout) :: f(0:p - 1)
    logical, optional, intent(in) :: invert
    integer(intkind) :: w, z, pz, x, y
    integer :: i, j, r, m
    logical :: inverse
    inverse = merge(invert, .false., present(invert))
    w = pow(root, (modu - 1) / p)
    if (inverse) w = inv(w)
    r = 0
    do i = 1, p - 2
      j = p / 2
      do
        r = xor(r, j)
        if (j <= r) exit
        j = j / 2
      end do
      if (i < r) call swap(f(i), f(r))
    end do
    m = 1
    do while (m < p)
      pz = 1
      z = pow(w, int(p / (2 * m), intkind))
      do i = 0, m - 1
        do j = i, p - 1, 2 * m
          x = f(j)
          y = mod(f(j + m) * pz, modu)
          f(j) = mod(x + y, modu)
          f(j + m) = modulo(x - y, modu)
        end do
        pz = mod(pz * z, modu)
      end do
      m = m * 2
    end do
    if (inverse) f = mod(f * inv(int(p, intkind)), modu)
  end
  integer(intkind) function pow(a, b) result(res)
    integer(intkind), intent(in) :: a, b
    integer(intkind) :: r, p
    res = 1
    r = b
    p = a
    do while (r > 0)
      if (btest(r, 0)) res = mod(res * p, modu)
      p = mod(p * p, modu)
      r = rshift(r, 1)
    end do
  end
  integer(intkind) function inv(a) result(res)
    integer(intkind), intent(in) :: a
    res = pow(a, modu - 2)
  end
  subroutine swap(a, b)
    integer(intkind), intent(inout) :: a, b
    a = xor(a, b)
    b = xor(a, b)
    a = xor(a, b)
  end
end module mod_ntt
program handshake
  use mod_ntt
  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(0:maxa), maxa, q(0:maxa), 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

Measured memory_bytes: 21996