program StackingBlocks; uses crt; type blockrec = record height:integer; number:integer; end; var infile,outfile:text; x,y,z:integer; blocks: array [1..12] of blockrec; n, t:integer; temp:blockrec; numberofblocks:integer; combcounter:integer; done:boolean; procedure findcombination(curheight: integer; curblock: integer; numblocks: integer); var x:integer; begin if curheight = t then begin combcounter:=combcounter + 1; if numblocks < numberofblocks then numberofblocks := numblocks; if combcounter > 1000 then done:=true; end else begin if curheight < t then begin if (curblock < n) and (numblocks < numberofblocks) then begin for x := blocks[curblock+1].number downto 0 do begin findcombination(curheight + x*blocks[curblock+1].height,curblock+1, numblocks + x); if done then x:=0; end; end; end; end; end; begin assign(infile,'DATA41.txt'); reset(infile); assign(outfile,'OUT41.txt'); rewrite(outfile); for x := 1 to 5 do begin readln(infile,n); for y:= 1 to n do readln(infile,blocks[y].height,blocks[y].number); readln(infile,t); for y:= 1 to n-1 do for z:= y+1 to n do begin if blocks[y].height < blocks[z].height then begin temp := blocks[y]; blocks[y] := blocks[z]; blocks[z] := temp; end; end; numberofblocks := 32700; combcounter := 0; done := false; for y := blocks[1].number downto 0 do begin findcombination(y*blocks[1].height,1,y); if done then y:=0; end; writeln(outfile,numberofblocks); end; close(infile); close(outfile); end.