type rucsac=record
x,y:longint;
end;

var  v:array[1..1000]of rucsac;
     use:array[1..1000,1..1000]of boolean;
     s:array[0..1000]of integer ;
     n,i,max,g:integer;

function maxi(a,b:integer):integer;
begin
if a>b then maxi:=a
else maxi:=b;
end;

procedure rez;
var i,j:integer;
begin
for i:=0 to g do
for j:=1 to n do begin
if (s[i]<>0) and (v[j].x+s[i]>s[v[i].y+i])and (use[i,j]=false)  then
begin
use[i,j+v[j].x]:=true;
s[i]:=v[i].x+s[j];
if v[i].x+j>max then max:=v[i].y+j;

end;
end;
end;

begin
assign(input,'rucsac.in');reset(input);
assign(output,'rucsac.out');rewrite(output);
read(n,g);
for i:=1 to n do begin
read(v[i].x,v[i].y);
if (v[i].x=1)and (v[i].y>max) then max:=v[i].y;
end;
s[0]:=0;
rez;
writeln(s[n]);
close(output);
end.