3回目のPOHが開催されてるみたいですね。
https://paiza.jp/poh/kirishima

さすがにこんな無茶な案件に関わったことはありませんが、妙にリアルなところもあって微妙な気分です。

解き方としては01ナップザック的なことになるんだと思うんですが、
たぶんもっと工夫する出来るところがあるんだろうなと思います。

rubyで挑戦してみました。

poh3.rb

m = gets.chomp.to_i
n = gets.chomp.to_i

dp = Array.new(m + 1,Float::INFINITY)
dp[0] = 0

n.times do
  num, cost = gets.chomp.split(/ /).map(&:to_i)
  
  ndp = Array.new(m + 1, Float::INFINITY)
  ndp[0] = 0
  
  (1 .. m).each do |j|
    prev = j - num
    prev = 0 if prev < 0
    
    non_use = dp[j]
    use = dp[prev] + cost
    if non_use < use
      ndp[j] = non_use
    else
      ndp[j] = use
    end
  end
  dp = ndp
end

puts dp[m]

運良く一発で通れました。
Array#minとか使うとすっきりするんですが、やっぱり遅くなるようでした。
が、やっぱり何倍も早い方いますねー。

結果
http://paiza.jp/poh/kirishima/result/09b509fc2be960b0927fcd0101e66d7e

追記1
Float::Infinityより、問題文からの最大値
INF = 500 * 5000000 + 1
を代わりに使うとなぜかもうちょっと早くなりました。

追記2　8/3

INF = 500 * 5000000 + 1
m, n = 2.times.map{gets.chomp.to_i}

dp = [0] + Array.new(m, INF)
n.times do
  num, cost = gets.chomp.split(/ /).map(&:to_i)
  m.downto(1) do |j|
    prev = j - num
    prev = 0 if prev < 0

    use = dp[prev] + cost
    dp[j] = use if use < dp[j]
  end
end

puts dp[m]

ちょっと改良してみましたが、どうにも一秒は切れないですねぇ。0.02秒のとかはどうしてるんだろう。
http://paiza.jp/poh/kirishima/result/5ba40ffef2d0c33a666fd0f98e48eaa5