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

var  v:array[1..1000]of rucsac;
     s:array[1..1000]of boolean;
     n,i,max,maxi,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; }
procedure rez;
var
begin
for i:=2 to g do
for j:=1 to n do begin
a[i,j]:=

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