program p1407;

var c,v:array[1..35000]of integer;

b,zz:array[1..100]of integer;

z,n,m,i,j,k,max:integer;

f:array[0..8000]of integer;

begin

readln(n,m);

for i:=1 to 3 do

readln(z,c[z],v[z]);

for i:=1 to n do

readln(b[i],zz[i]);

for i:=1 to n do

for j:=m-(b[i]+v[zz[i]]*b[i]) downto 0 do

if f[j+(b[i]+v[zz[i]]*b[i])]