! 32bit整数型可変長配列のモジュール
module mod_vector
    implicit none
    private
    type :: vector
        integer :: N ! 配列の意味のある長さ
        integer, allocatable :: array(:) ! 配列
    end type vector

    public :: vector
    public :: vec_make, vec_push_back, vec_size, vec_index
    public :: vec_pop_back, vec_change

contains

    ! 初期化
    subroutine vec_make(vec)
        implicit none
        type(vector) :: vec
        allocate(vec%array(5))
        vec%N = 0
        return
    end subroutine vec_make

    ! vectorの大きさを取得
    function vec_size(vec) result(ret)
        implicit none
        type(vector) :: vec
        integer :: ret
        ret = vec%N
        return
    end function vec_size

    ! 末尾にxを追加
    subroutine vec_push_back(vec, x)
        implicit none
        type(vector) :: vec
        integer, allocatable :: tmp(:)
        integer :: x
        integer :: N

        N = vec%N
        if(N < size(vec%array)) then
            vec%array(N + 1) = x
            vec%N = N + 1
        else
            allocate(tmp(N))
            tmp = vec%array
            deallocate(vec%array)
            allocate(vec%array(2*N))
            vec%array(1:N) = tmp
            vec%array(N + 1) = x
            vec%N = N + 1
        end if
        return
    end subroutine vec_push_back

    ! 末尾の要素を削除
    subroutine vec_pop_back(vec)
        implicit none
        type(vector) :: vec
        vec%N = vec%N - 1
        return
    end subroutine vec_pop_back

    ! i番目の要素を取得
    function vec_index(vec, i) result(ret)
        implicit none
        type(vector) :: vec
        integer :: i, ret
        ret = vec%array(i)
        return
    end function vec_index

    ! i番目の要素をxに変更
    subroutine vec_change(vec, i, x)
        implicit none
        type(vector) :: vec
        integer :: i, x
        vec%array(i) = x
        return
    end subroutine vec_change
end module mod_vector
! 32bit整数型heapのモジュール
! 可変長配列のモジュールに依存している
module mod_priority_queue
    use mod_vector
    implicit none
    private
    type :: pq
        type(vector) :: vec
    end type pq

    public :: pq
    public :: pq_make, pq_push, pq_pop, pq_top, pq_size, pq_empty
contains
    subroutine swap(a, b)
        implicit none
        integer, intent(inout) :: a, b
    
        integer :: c
    
        c = a
        a = b
        b = c
    end subroutine swap

    !
    ! 初期化
    !
    subroutine pq_make(heap)
        implicit none
        type(pq) :: heap
        call vec_make(heap%vec)
        return
    end subroutine pq_make

    !
    ! heapにxを追加
    !
    subroutine pq_push(heap, x)
        implicit none
        type(pq) :: heap
        integer :: x, i, n
        
        call vec_push_back(heap%vec, x)
        n = vec_size(heap%vec)
        i = n
        do while( i >= 2 )
            if (heap%vec%array(i) > heap%vec%array(i/2)) then 
                call swap(heap%vec%array(i), heap%vec%array(i/2))
            else
                exit
            end if
            i = i / 2
        end do
        return
    end subroutine pq_push

    !
    ! heapの先頭を削除
    !
    subroutine pq_pop(heap)
        implicit none
        type(pq) :: heap
        integer :: i, n

        n = vec_size(heap%vec)
        call swap(heap%vec%array(1), heap%vec%array(n))
        call vec_pop_back(heap%vec)

        n = n - 1
        i = 1
        if( mod(n, 2) == 1 ) then
        do while(i <= n/2)
            if(heap%vec%array(i) < heap%vec%array(2*i) .or. heap%vec%array(i) < heap%vec%array(2*i + 1)) then
            if(heap%vec%array(2*i) > heap%vec%array(2*i + 1)) then
                call swap(heap%vec%array(i), heap%vec%array(2*i))
                i = 2*i
            else
                call swap(heap%vec%array(i), heap%vec%array(2*i + 1))
                i = 2*i + 1
            end if
            else
            exit
            end if
        end do
        else
        do while(i <= n/2 - 1)
            if(heap%vec%array(i) < heap%vec%array(2*i) .or. heap%vec%array(i) < heap%vec%array(2*i + 1)) then
            if(heap%vec%array(2*i) > heap%vec%array(2*i + 1)) then
                call swap(heap%vec%array(i), heap%vec%array(2*i))
                i = 2*i
            else
                call swap(heap%vec%array(i), heap%vec%array(2*i + 1))
                i = 2*i + 1
            end if
            else
            exit
            end if
        end do
        if( heap%vec%array(n/2) < heap%vec%array(n) ) then
            call swap(heap%vec%array(n/2), heap%vec%array(n))
        end if
        end if   
        return
    end subroutine pq_pop

    !
    ! heapの最大値を取得
    !
    integer function pq_top(heap) result(ret)
        implicit none
        type(pq) :: heap
        ret = heap%vec%array(1)
        return
    end function pq_top

    !
    ! heapの大きさを取得
    !
    integer function pq_size(heap) result(ret)
        implicit none
        type(pq) :: heap
        ret = vec_size(heap%vec)
        return
    end function pq_size

    !
    ! heapが空ならtrueを返す
    !
    logical function pq_empty(heap) result(ret)
        implicit none
        type(pq) :: heap
        if (vec_size(heap%vec) == 0) then
            ret = .true.
        else
            ret = .false.
        end if
        return
    end function pq_empty
end module mod_priority_queue

module mod_sort
    implicit none
    private
    
    interface sort
        module procedure msort_int4, msort_int8, msort_int16, msort_string
    end interface sort

    interface swap
        module procedure swap_int4, swap_int8, swap_int16, msort_string
    end interface swap

    public :: sort
        
contains
    subroutine swap_int4(a, b)
        implicit none
        integer, intent(inout) :: a, b
        integer :: c

        c = a
        a = b
        b = c

    end subroutine swap_int4

    recursive subroutine msort_int4(x)
        implicit none
        integer, intent(inout) :: x(:)
        integer :: n, mid, i, j, k
        integer, allocatable :: tmp(:)

        n = size(x)

        if(n == 1) then
            return
        end if

        mid = n / 2
        call msort_int4(x(:mid))
        call msort_int4(x(mid+1:))

        allocate(tmp(n))
        tmp = x

        do k = n, mid+1, -1
            tmp(k) = x(mid + n - k + 1)
        end do

        i = 1
        j = n

        do k = 1, n
            if(tmp(i) <= tmp(j)) then
            x(k) = tmp(i)
            i = i + 1
            else
            x(k) = tmp(j)
            j = j - 1
            end if
        end do

        deallocate(tmp)
        return
    end subroutine msort_int4

    subroutine swap_int8(a, b)
        implicit none
        integer(8), intent(inout) :: a, b
        integer(8) :: c

        c = a
        a = b
        b = c

    end subroutine swap_int8

    recursive subroutine msort_int8(x)
        implicit none
        integer(8), intent(inout) :: x(:)
        integer :: n, mid, i, j, k
        integer(8), allocatable :: tmp(:)

        n = size(x)

        if(n == 1) then
            return
        end if

        mid = n / 2
        call msort_int8(x(:mid))
        call msort_int8(x(mid+1:))

        allocate(tmp(n))
        tmp = x

        do k = n, mid+1, -1
            tmp(k) = x(mid + n - k + 1)
        end do

        i = 1
        j = n

        do k = 1, n
            if(tmp(i) <= tmp(j)) then
            x(k) = tmp(i)
            i = i + 1
            else
            x(k) = tmp(j)
            j = j - 1
            end if
        end do

        deallocate(tmp)
        return
    end subroutine msort_int8

    subroutine swap_int16(a, b)
        implicit none
        integer(16), intent(inout) :: a, b
        integer(16) :: c

        c = a
        a = b
        b = c

    end subroutine swap_int16

    recursive subroutine msort_int16(x)
        implicit none
        integer(16), intent(inout) :: x(:)
        integer :: n, mid, i, j, k
        integer(16), allocatable :: tmp(:)

        n = size(x)

        if(n == 1) then
            return
        end if

        mid = n / 2
        call msort_int16(x(:mid))
        call msort_int16(x(mid+1:))

        allocate(tmp(n))
        tmp = x

        do k = n, mid+1, -1
            tmp(k) = x(mid + n - k + 1)
        end do

        i = 1
        j = n

        do k = 1, n
            if(tmp(i) <= tmp(j)) then
            x(k) = tmp(i)
            i = i + 1
            else
            x(k) = tmp(j)
            j = j - 1
            end if
        end do

        deallocate(tmp)
        return
    end subroutine msort_int16

    subroutine swap_string(a, b, d)
        implicit none
        integer :: d
        character(d), intent(inout) :: a, b
        character(d) :: c

        c = a
        a = b
        b = c

    end subroutine swap_string

    recursive subroutine msort_string(x, d)
        implicit none
        integer :: d
        character(d), intent(inout) :: x(:)
        integer :: n, mid, i, j, k
        character(d), allocatable :: tmp(:)

        n = size(x)

        if(n == 1) then
            return
        end if

        mid = n / 2
        call msort_string(x(:mid), d)
        call msort_string(x(mid+1:), d)

        allocate(tmp(n))
        tmp = x

        do k = n, mid+1, -1
            tmp(k) = x(mid + n - k + 1)
        end do

        i = 1
        j = n

        do k = 1, n
            if(tmp(i) <= tmp(j)) then
            x(k) = tmp(i)
            i = i + 1
            else
            x(k) = tmp(j)
            j = j - 1
            end if
        end do

        deallocate(tmp)
        return
    end subroutine msort_string
end module mod_sort

program probc
    use mod_vector
    use mod_priority_queue
    use mod_sort
    implicit none
    type(pq) :: h
    integer, allocatable :: a(:), b(:)
    integer :: N, M, i, ans, ind, j
    integer, allocatable :: s(:)

    read(*,*) N, M
    allocate(a(N), b(N), s(N))
    do i = 1, N
        read(*,*) a(i), b(i)
    end do  

    s = a * 10001 + b
    call sort(s)
    do i = 1, N
        a(i) = s(i) / 10001
        b(i) = mod(s(i), 10001)
    end do

    call pq_make(h)
    
    ans = 0
    ind = 1
    do i = 1, M
        do while(ind <= N .and. a(ind) <= i)
            call pq_push(h, b(ind))
            ind = ind + 1
        end do
        if(pq_empty(h)) then
            cycle
        end if
        ans = ans + pq_top(h)
        call pq_pop(h)
    end do

    write(*,*) ans
    deallocate(a, b, s)
    stop
contains
end program probc

Measured memory_bytes: 4612