module mod_priority_queue
  implicit none
  type t_priority_queue
    private
    integer :: num = 0 !中に入ってる物の数
    integer, pointer :: heap(:) => null()!pqの容量
  contains
    procedure :: offer => offer
    procedure :: clear => clear
    procedure :: poll => poll
    procedure :: peek => peek
    procedure :: size => size_of
  end type t_priority_queue
  
contains

  subroutine offer(pq,item)
    class(t_priority_queue), intent(inout) :: pq
    integer, intent(in) :: item
    integer :: n, i, t
    integer, allocatable :: tmp(:)
    if (.not.associated(pq%heap)) allocate(pq%heap(1))
    
    !いっぱいいっぱいのときには拡張している
    if (pq%num == size(pq%heap)) then
      allocate(tmp(pq%num))
      tmp = pq%heap
      deallocate(pq%heap)
      allocate(pq%heap(2*pq%num))
      pq%heap(1:pq%num) = tmp
      deallocate(tmp)
    end if
    
    pq%num = pq%num+1
    pq%heap(pq%num) = item
    n = pq%num
    do while (n > 1)
      i = n/2
      if (pq%heap(n) > pq%heap(i)) then
        t = pq%heap(n)
        pq%heap(n) = pq%heap(i)
        pq%heap(i) = t
      end if
      n = i
    end do
    return
  end subroutine offer
  
  subroutine clear(pq)
    class(t_priority_queue), intent(inout) :: pq
    if (associated(pq%heap)) deallocate(pq%heap)
    pq%num = 0
    return
  end subroutine clear

  function poll(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item, n, i, j, tmp
    n = pq%num
    item = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. pq%heap(j+1) > pq%heap(j)) j = j+1
      if (pq%heap(j) > pq%heap(i)) then
        tmp = pq%heap(j)
        pq%heap(j) = pq%heap(i)
        pq%heap(i) = tmp
      end if
      i = j
    end do
  end function poll
  
  function peek(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item
    item = pq%heap(1)
  end function peek
  
  integer function size_of(pq)
    class(t_priority_queue), intent(in) :: pq
    size_of = pq%num
  end function size_of
end module mod_priority_queue

use mod_priority_queue
integer N,M,K
integer,allocatable,dimension(:)::A,B
type(t_priority_queue) :: pq
integer(16) ans
read*,N,M
allocate(A(N),B(N))
do i=1,N
  read*,A(i),B(i)
end do

call HeapsortPair(N,A,B)

ans=0;k=1
do i=1,M
  do while(K<=N .and. A(K)<=i)
    call offer(pq,B(K))
    K=K+1
  end do
  if(size_of(pq)/=0)ans=ans+poll(pq)
end do

print"(i0)",ans

contains

subroutine HeapsortPair(n,array,array2)
  implicit none
!ここの入力は状況に応じて変更すること
  integer,intent(in) :: n
  integer,intent(inout) :: array(1:n),array2(1:n)
  integer::i,k,j,l
  integer:: t,t2

  l=n/2+1
  k=n
  do while(k /= 1)
     if(l > 1)then
        l=l-1
        t=array(L)
        t2=array2(L)
     else
        t=array(k)
        t2=array2(k)
        array(k)=array(1)
        array2(k)=array2(1)
        k=k-1
        if(k == 1) then
           array(1)=t
           array2(1)=t2
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j<=k)
        if(j < k)then
           if(array(j) < array(j+1))j=j+1
        endif
        if (t < array(j))then
           array(i)=array(j)
           array2(i)=array2(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
     array2(i)=t2
  enddo
  return
end subroutine HeapsortPair

end

Measured memory_bytes: 1596