program main
      implicit none
      integer :: h, n, i, j, k, l
      integer, allocatable :: a(:), b(:)
      integer(8), allocatable :: dp(:)

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

      allocate( dp(0:h) )
      dp(:) = 10**9
      dp(0) = 0
      do i = 1, h
        do j = 1, n
          k = i - a(j)
          if ( k < 0 ) k = 0
          dp(i) = min( dp(i), b(j) + dp(k)  )
        end do
      end do

      print *, dp(h)

end program main
