いろいろ途中で計算を止める方法を思考錯誤した結果、適当な回数でやめるというずるい回答。 http://paiza.jp/poh/kirishima/result/9f3aeb62ec2814552a7da9e656b41959

paiza.rb

m = gets.to_i
n = gets.to_i
qrs = []
min_cost = 5000000+1
max_human = 0

n.times do
  human,cost = gets.split.map(&:to_i)
  max_human += human
  min_cost = cost if min_cost > cost
  qrs << [human,cost]
end

qrs.sort! { |b,a| b[1] / b.first <=> a[1] / a.first }
# qrs.sort! { |a,b| b.first <=> a.first }


tmp_human = max_human
queue = []
qs = qrs.dup
until qs.empty?
  queue << [qs.dup,0,0, tmp_human]
  human,cost = qs.shift
  tmp_human -= human
end

result = nil

i=0
until queue.empty?
  i+=1
  context = queue.shift
  qrs, total_human, total_cost, remain_human = context
  human,cost = qrs.shift
  remain_human -= human

  next_human = human + total_human
  next_cost = cost + total_cost

#  p ["desc", m, next_human, next_cost, human, cost, remain_human, qrs]
  if next_human < m
    next if result && next_cost + min_cost > result
    if qrs.size == 0
      next
    end

    q = qrs.dup
    remain = remain_human
    sub_queue = []
    while qrs.size > 0
      if m > next_human + remain
#        p ["skip",i, m, next_human, remain, qrs.size]
        break
      end
      sub_queue << [qrs.dup, next_human, next_cost, remain_human]
      human, cost = qrs.shift
      remain -= human
    end
    queue = sub_queue + queue
    next
  end

  result = next_cost if result.nil?
  if result > next_cost
    result = next_cost
#    p ["resulct",i,next_cost]
  end

  break if i > 1000
end

puts result
# p [i,result]