require 'set'

def bfs(start_node, extra = nil)
    return 0 if start_node.is_goal?(extra)
    reached = Set[start_node]
    dist = 1
    queue = [start_node]
    until queue.empty?
        next_queue = []
        until queue.empty?
            node = queue.shift
            node.each_next_node(extra) do |next_node|
                return dist if next_node.is_goal?(extra)
                next if reached.include?(next_node)
                reached << next_node
                next_queue << next_node
            end
        end
        dist += 1
        queue = next_queue
    end
    return nil
end

class Array
    def is_goal?(extra)
        self[0] <= 0
    end

    def each_next_node(extra)
        d, t = self
        (extra[:valid_weapons][t] || []).each do |a, e|
            ne = t + e
            ne = extra[:max_e] if ne > extra[:max_e]
            yield [d - a, ne]
        end
    end
end

loop do
    d, n = gets.split.map(&:to_i)
    break if n == 0
    weapons = (1..n).map { gets.split.map(&:to_i) }
    weapons.sort_by!(&:last)
    valid_weapons = {}
    (0..weapons[-1][2]).each do |t|
        l = weapons.select {|a, e, r| r <= t}
        l.map! {|a, e, _| [a, e]}
        l.uniq!
        l = l.select {|a1, e1| l.all?{|a2, e2| (a1 == a2 && e1 == e2) || (a1 > a2 || e1 > e2)}}
        valid_weapons[t] = l
    end
    puts bfs([d, 0], {:valid_weapons => valid_weapons, :max_e => weapons[-1][2]}) || 'NA'
end

