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

var  v:array[1..1000]of rucsac;
     a:array[1..1000,1..1000]of integer;
     n,i,max,g:integer;

{procedure rez;
var i,j:integer;
begin
for i:=1 to n do begin
if s[v[i].x]=true then
for j:=max downto 1 do
 if s[j]=true and (s[j+v[i].x]=false) then begin
 s[j+v[i].x]:=true;
 if j+v[i].x>maxi then maxi:=j+v[i].x;
end;
if maxi>max then max:=maxi;

end; }
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:=2 to g do
for j:=1 to n do begin
a[i,j]:=maxi(a[i-1,i],(a[i-1][i-v[j].x]+v[j].y));

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>max then max:=v[i].x;
end;
a[1,1]:=max;
rez;
close(output);
end.