fun main(args:Array<String>?): Unit {
    while(true){
        val (d, n) = readLine()!!.trim().split(' ').map(String::toInt)
        if (n == 0) return
        val tools = Array(n){
            val (a, e, r) = readLine()!!.trim().split(' ').map(String::toInt)
            Tool(a, e, r)
        }
        println(
                solve(d, tools) ?: "NA"
        )
    }
}
fun solve(treeHealth: Int, tools: Array<Tool>): Int? {
    if (tools.none{it.experienceNeed == 0 && (it.experienceGain > 0 || it.damage > 0)}) return null
    val sorted = tools.filterNot{it.damage == 0 && it.experienceGain == 0}.sortedBy(Tool::experienceNeed)
    val maxExperience = sorted.maxBy(Tool::experienceNeed)!!.experienceNeed
    val memo = Array(treeHealth + 1){Array(maxExperience + 1){Array(tools.size){null as Int?}}}
    fun sub(health: Int, experience: Int, tool: Int): Int? {
        return when{
            health <= 0 -> 0
            tool >= sorted.size -> null
            memo[health][experience][tool] != null -> memo[health][experience][tool]
            experience < sorted[tool].experienceNeed -> null
            sorted[tool].damage == 0 && experience == maxExperience -> {
                memo[health][experience][tool] = sub(health, experience, tool + 1)
                memo[health][experience][tool]
            }
            else -> {
                memo[health][experience][tool] = listOf(sub(health - sorted[tool].damage, minOf(maxExperience, experience + sorted[tool].experienceGain), tool)?.let{it + 1}, sub(health, experience, tool + 1)).filterNotNull().min()
                memo[health][experience][tool]
            }
        }
    }
    return sub(treeHealth, 0, 0)
}
data class Tool(val damage: Int, val experienceGain: Int, val experienceNeed: Int)
