Main.rb

# POH3 // DP

m = gets.to_i
n = gets.to_i

dp = Array.new(m+1, 9999999999999)
dp[0] = 0

n.times{
    q, r = gets.split.map(&:to_i)
    m.downto(0).each{|i|
        q2 = [i+q, m].min
        dp[q2] = [dp[q2], dp[i]+r].min
    }
}

puts dp[m]