type combinatie=record
       g:smallint;
       p:longint;
     end;
var n,i,t,mx,gr,pr,max,tnou:longint;
    a:array[0..100005]of combinatie;
    aj:array[0..10005]of boolean;
    bufin:array[1..65000]of byte;

procedure add(x,y:longint);
begin
  inc(tnou);
  a[t+tnou].g := x;
  a[t+tnou].p := y;
end;


procedure Creeaza(g,p:longint);
var i,j,tl:longint;
begin
  tnou := 0;

  add(g,p);
  for i := 1 to t do
    if g+a[i].g <= mx then
      add(g+a[i].g,p+a[i].p);

  tl := 0;
  for i := t+1 to t+tnou do
  begin
    if aj[a[i].g] then
    begin
      for j := 1 to t do
        if a[i].g = a[j].g then
        begin
          if a[i].p > a[j].p then a[j].p := a[i].p;
          break;
        end;
    end
    else
    begin
      inc(tl); aj[a[i].g] := true;
      a[t+tl].g := a[i].g;
      a[t+tl].p := a[i].p;
    end;
  end;

  t := t + tl;
end;

begin
  assign(input,'rucsac.in'); reset(input);
  assign(output,'rucsac.out'); rewrite(output);

  readln(n,mx);

  for i := 1 to mx do aj[i] := false;
  t := 0;

  for i := 1 to n do
  begin
    readln(gr,pr);
    Creeaza(gr,pr);
  end;

  max := a[1].p;
  for i := 2 to t do
    if a[i].p > max then max := a[i].p;

  writeln(max);


  close(input);
  close(output);
end.