记录编号	15398	评测结果	AAAAAA
题目名称	[POI 1997] 阿里巴巴	最终得分	100
用户昵称	ZhouZn1	是否通过	通过
代码语言	Pascal	运行时间	0.024 s
提交时间	2009-11-12 18:19:09	内存使用	16.35 MiB

program ali;
type
        rec=record
        zz,ss,mm:longint;
        dep:integer;
        end;
        rec1=record
        z1,s1,m1,z2,s2,m2:integer;
        end;
var
        i,j,d,zp,sp,mp,z,s,m,head,tail,zt,st,mt:longint;
        r:byte;
        list:array[1..1000000]of rec;
        rr:array[1..10]of rec1;
        v:array[0..100,0..100,0..100]of boolean;
procedure init;
begin
        readln(zp,sp,mp);
        readln(z,s,m);
        readln(r);
        for i:=1 to r do
        with rr[i] do
        readln(z1,s1,m1,z2,s2,m2);
        fillchar(v,sizeof(v),0);
end;
function check(ii:integer;var zz1,ss1,mm1:longint):boolean;
begin
        if zz1-rr[ii].z1<0 then exit(false);
        if ss1-rr[ii].s1<0 then exit(false);
        if mm1-rr[ii].m1<0 then exit(false);
        zz1:=zz1-rr[ii].z1;
        ss1:=ss1-rr[ii].s1;
        mm1:=mm1-rr[ii].m1;
        exit(true);
end;
procedure main;
var
        i:integer;
        zn,sn,mn{,zt,st,mt}:longint;
begin
        head:=0;
        tail:=1;
        with list[1] do
        begin
        zz:=zp;
        ss:=sp;
        mm:=mp;
        dep:=0;
        end;
        v[zp,sp,mp]:=true;
        repeat
                inc(head);
                for i:=1 to r do
                begin
                zn:=list[head].zz;
                sn:=list[head].ss;
                mn:=list[head].mm;
                if check(i,zn,sn,mn) then
                begin
                        zt:=zn+rr[i].z2;
                        st:=sn+rr[i].s2;
                        mt:=mn+rr[i].m2;
                        if (zt>=z)and(st>=s)and(mt>=m) then
                        begin
                        writeln(list[head].dep+1);
                        exit;
                        end; //ans
                        if (zt>z*10)or(mt>m*10)or(st>s*10) then
                        begin
                        break;
                        end;
                        if not(v[zt,st,mt]) then
                        begin
                                inc(tail);
                                with list[tail] do
                                begin
                                        zz:=zt;
                                        ss:=st;
                                        mm:=mt;
                                        dep:=list[head].dep+1;
                                end;
                                v[zt,st,mt]:=true;
                        end;
                end;
                end;
        until head>tail;
        writeln('NIE');
end;
begin
        assign(input,'ali.in');
        reset(input);
        assign(output,'ali.out');
        rewrite(output);
        readln(d);
        while d>0 do
        begin
        dec(d);
        init;
        main;
        end;
        close(input);
        close(output);
end.