program main
    implicit none
    integer(4):: h, n, i, j, k
    integer(4), allocatable:: a(:), b(:), dp(:), old_dp(:)
    integer(4), parameter:: inf = 10000000
    logical:: change = .true.

    read*, h,n
    allocate(a(n),b(n),dp(0:h), old_dp(0:h))

    do i = 1,n
        read*, a(i), b(i)
    end do

    dp(1:) = inf
    dp(0) = 0

    

    do while(change)
        old_dp(:) = dp(:)
        do i = 0, h
            do j = 1, n
                if (i+a(j) <= h) then
                    dp(i+a(j)) = min(dp(i+a(j)), dp(i)+b(j))
                else
                    dp(h) = min(dp(h), dp(i)+b(j))
                end if
            end do
        end do

        change = .false.
        do i = 0, h
            if (dp(i) /= old_dp(i))then
                change = .true.
                exit
            end if
        end do       
    end do

    print*, dp(h)

end program main