巨樹の刻み手

あなたは N 種類の道具を使って、目の前の巨樹を切り倒そうとしています。はじめは、樹の耐久力は D、あなたの経験値は 0 ですが、道具 i で１回樹を叩くと樹の耐久力は a_i 減り、あなたは e_i の経験値を得ます。ただし、道具 i を使うためには、あなたは r_i 以上の経験値を持っていなければなりません。樹の耐久力が 0 以下になると樹は倒れます。

樹の耐久力と道具についての情報が与えられたとき、樹を切り倒すには最低何回樹を叩かなければいけないかを求めるプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。

D N
a1 e1 r1
a2 e2 r2
:
aN eN rN

1 行目に樹の耐久力を表す整数 D (1 ≤ D ≤ 100) と道具の種類の数 N(1 ≤ N ≤ 100) が与えられる。続く N 行に道具 1 から N までの情報が与えられる。a_i (0 ≤ a_i ≤ 100) と e_i (0 ≤ e_i ≤ 100) は、道具iを１回使うことで減る樹の耐久力とあなたが得ることのできる経験値をそれぞれ表す。r_i (0 ≤ r_i ≤ 100) は道具を使うために必要な経験値を表す。a_i, e_i, r_i はすべて整数である。

データセットの数は 50 を超えない。

出力

樹を切り倒すのに必要な、樹を叩く最小の回数を１行に出力する。ただし、樹を切り倒すことが不可能な場合は NA と出力する。

入出力例

入力例

15 4
1 1 0
1 2 2
5 10 5
8 1 15
60 4
5 2 0
8 8 2
3 5 0
49 0 18
100 1
1 1 1
0 0

出力例

6
4
NA