type vec=record
x:longint;
y:longint;
end;

type vector=array[1..5000]of longint;
var max,n,gr,i:longint;
    sum,d,cost:vector;
    v:array[1..5000]of vec;
procedure solve;
var i,j:longint;
begin
for i:=1 to n do
for j:=max downto 1 do
if (sum[j]=1)and(i<>d[j])  then
  begin
  sum[v[i].x+j]:=1;
  d[v[i].x+j]:=i;
  inc(cost[v[i].x+j],v[i].y);
  if v[i].x+j>max then max:=v[i].x+j;

  end;

end;

begin
assign(input,'rucsac.in');reset(input);
assign(output,'rucsac.out');rewrite(output);
read(n,gr);
max:=0;
for i:=1 to n do
 begin
 read(v[i].x,v[i].y);
 sum[v[i].x]:=1;
 if v[i].x>max then max:=v[i].x;
 if v[i].y>cost[v[i].x]then
  begin
  cost[v[i].x]:=v[i].y;
  d[v[i].x]:=i;
  end;
 end;
solve;
close(output);
end.