program crested_ibis_vs_monster
  implicit none
  integer :: h, n, a(1000) = 0, b(1000) = 0, i, j, dp(0:20000) = 1e9
  read(*,*) h, n
  do i = 1, n
    read(*,*) a(i), b(i)
  end do
  dp(0) = 0
  do j = 1, 20000
    do i = 1, n
      if (a(i) > j) cycle
      dp(j) = min(dp(j),dp(j-a(i))+b(i))
    end do
  end do
  write(*,'(i0)') minval(dp(h:))
end program crested_ibis_vs_monster