Main.rb

# POH 3 // greedy

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

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

def calc(i, engineers, cost)
    if i == @n
        if engineers >= @m
            return cost
        else
            return 999999999999
        end
    end
    
    ret1 = calc(i+1, engineers, cost)
    ret2 = calc(i+1, engineers+@companies[i][0], cost+@companies[i][1])
    return [ret1, ret2].min
end

puts calc(0, 0, 0)