program rucsac;

var fi,fo:text;
    castig:array[0..5000,0..5000]of integer;
    alege:array[0..5000,0..5000]of integer;
    n,g:integer;
    gr,c:array[1..5000]of integer;

  procedure citiredate;
  var i:integer;
  begin
      readln(fi,n,g);
      for i:=1 to n do
        begin
            read(fi,gr[i],c[i]);
        end;
  end;



  procedure dinamique;
  var i,j:integer;
  begin
      for i:=1 to n do
        for j:=1 to g do
          if j>=gr[i] then
            begin
                if castig[i-1,j]<castig[i-1, j-gr[i]]+c[i] then
                  begin
                      castig[i,j]:=castig[i-1,j-gr[i]]+c[i];
                      alege[i,j]:=i;
                  end
                else
                  begin
                      castig[i,j]:=castig[i-1,j];
                      alege[i,j]:=alege[i-1,j];
                  end;
            end
          else
            begin
                 castig[i,j]:=castig[i-1,j];
                 alege[i,j]:=alege[i-1,j];
            end;
      writeln(Fo, castig[n,g]);

  end;

  procedure drum;
  var i,j:integer;
  begin
      i:=n; j:=g;
      while alege[i,j]<>0 do
        begin
            writeln('ob. ',alege[i,j], ' cu greut. ', gr[alege[i,j]], ' si castigul ', c[alege[i,j]]);

            j:=j-gr[alege[i,j]];
            i:=i-1;
        end;
  end;


begin
    assign(fi,'rucsac.in'); reset(fi);
    assign(fo,'rucsac.out'); rewrite(fo);

      citiredate;

      dinamique;

      drum;

    close(fi); close(Fo);
end.