Calorie Counting

Time Limit : 1 sec, Memory Limit : 65536 KB

カロリー計算

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

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

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

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

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

入力

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

1行目 お菓子の数n(整数)
2行目 第1のお菓子の情報 i p q r(整数 整数 整数 整数;半角空白区切り)
3行目 第2のお菓子の情報

n+1番目 第nのお菓子の情報
n+2番目 各栄養素及びカロリーの制限値 P Q R C(整数 整数 整数 整数;半角空白区切り)

出力

入力データセットごとに、食べてもよいお菓子の番号または”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/