Main.rb

# POH 3 // greedy, bit

@m = gets.to_i
@n = gets.to_i

@companies = []
@n.times{
    q, r = gets.split.map(&:to_i)
    @companies.push([q, r])
}

mincost = 99999999999
(0..2**@n).each{|i|
    engineers = 0
    cost = 0
    (0...@n).each{|j|
        if (i & (1<<j) != 0) then
            engineers += @companies[j][0]
            cost += @companies[j][1]
        end
    }
    if engineers >= @m
        mincost = [mincost, cost].min
    end
}
puts mincost