program ABC153E
    implicit none
    integer(8)::H,N,div,i,j
    integer(8),allocatable,dimension(:)::A,B
    integer(8),allocatable,dimension(:,:)::dp

    read(5,*)H,N
    allocate(A(N))
    allocate(B(N))
    allocate(dp(H,N))

    do i=1,N
        read(5,*)A(i),B(i)
    end do

    do i=1,N
        do j=1,H
            if(i==1)then
                div=j/A(i)
                if(mod(j,A(i))/=0)then
                    div=div+1
                end if
                dp(j,i)=B(i)*div
            else
                if(j<=A(i))then
                    dp(j,i)=min(dp(j,i-1),B(i))
                else
                    dp(j,i)=min(dp(j,i-1),dp(j-A(i),i)+B(i))
                end if
            end if
        end do
    end do

    print'(i0,1x,i0)',H,N
    print'(i0)',dp(H,N)
end program ABC153E