program taskak;
type vektor=array[1..10000] of longint;
var v1,v2:vektor;
    i,j,n,s,w,p:longint;
    f,g:text;
procedure kombinal(var v1,v2:vektor; s,j:integer);
var i,w,p:integer;
begin
  readln(f,w,p);
  if p>v2[w] then v2[w]:=p;
  for i:=1 to s-w do
    if (v1[i]<>0) and (v1[i+w]<v1[i]+p) then v2[i+w]:=v1[i]+p;

read
end;
begin
  assign(f,'rucsac.in');
  reset(f);
  readln(f,n,s);
  readln(f,w,p);
  v1[w]:=p;
  for j:=2 to n do
    begin
      for i:=1 to s do
       v1[i]:=v2[i];
      kombinal(v1,v2,s,j);
    end;
  close(f);
  w:=0;
  for i:=1 to s do
    begin
      if v2[i]>w then w:=v2[i];
    end;
assign(g,'rucsac.out');
rewrite(g);
write(g,w);
close(g);
end.