program main
  implicit none
  integer :: h, n, i, j
  integer, allocatable :: m(:), a(:), b(:)
  read (*, *) h, n
  allocate (m(0:h), a(n), b(n))
  do i = 1, n
    read *, a(i), b(i)
  end do

  ! m(d) は d ダメージ与えるために必要な最小 MP
  m(:) = 10 ** 9
  m(0) = 0

  ! もらう DP
  do j = 1, h
    do i = 1, n
      m(j) = min(m(j), b(i) + m(max(0, j - a(i))))
    end do
  end do

  print "(i0)", m(h)
end program main
