Calorie Counting

Time Limit : 1 sec, Memory Limit : 65536 KB

カロリー計算

食べ物には3大栄養素と呼ばれる「たんぱく質」「脂質」「炭水化物」の3つの栄養素が含まれています。1g(グラム)あたりたんぱく質と炭水化物は 4 kcal(キロカロリー)、脂質は 9 kcal と計算されます。たとえば、下の表によると番号1のケーキにはタンパク質 7 g、脂質 14 g、炭水化物 47 g が含まれています。これをもとに含まれるカロリーを計算すると、4 × 7 + 9 × 14 + 4 × 47 = 342 kcal となります。その他も同様に計算されています。

番号名前たんぱく質(g)脂質(g)炭水化物(g)カロリー(kcal)
1ケーキ71447342
2ポテトチップス53555555
3どら焼き6359287
4プリン6515129

分類の対象となるお菓子の個数 n と各お菓子の情報、制限の情報を入力とし、そのお菓子一つだけなら制限を超えることがない(食べてもよい)お菓子の一覧を出力するプログラムを作成してください。

お菓子の情報は、お菓子の番号 s、そのお菓子に含まれるたんぱく質の重量 p、脂質の重量 q、炭水化物の重量 r から構成されています。制限の情報には、含むことができる最大のたんぱく質の重量 P、脂質の重量 Q、炭水化物の重量 R、および摂取することができる最大のカロリー C からなっており、タンパク質、脂質、炭水化物、カロリーのいずれかの一つでも超えると制限違反となり、「食べてはいけないお菓子」と判断されます。

食べてもよいお菓子の一覧は、食べてもよいお菓子の番号を入力順に出力してください。なお、食べてもよいお菓子がなければ”NA”と出力してください。 上の表にある4個のお菓子について、P = 10, Q = 15, R = 50, C = 400 という制限の場合、ケーキとプリンはそれぞれの栄養素及びカロリーが制限値以下なので食べてもよいお菓子に分類されますが、ポテトチップスは炭水化物とカロリー、どら焼きは炭水化物の量が制限値を超えているため食べてはいけないお菓子に分類されます。

入力

複数のデータセットの並びが与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
s1 p1 q1 r1
s2 p2 q2 r2
:
sn pn qn rn
P Q R C

1行目にお菓子の数 n (1 ≤ n ≤ 1000)が与えられます。続く n 行に第 i のお菓子の番号 si (1 ≤ si ≤ 1000)、各栄養素の重量を表す整数 pi, qi, ri (0 ≤ pi, qi, ri ≤ 100) が与えられます。

続く行に各栄養素及びカロリーの制限値を表す整数 P, Q, R (0 ≤ P, Q, R ≤ 100), C (0 ≤ C ≤ 1700) が与えられます。

データセットの数は 100 を超えません。

出力

データセットごとに、食べてもよいお菓子の番号または ”NA” を出力します。

入力例

4
1 7 14 47
2 5 35 55
3 6 3 59
4 6 5 15
10 15 50 400
2
1 8 10 78
2 4 18 33
10 10 50 300
0

出力例

1
4
NA

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/