mkmoney

var i,j,k,m,n,v,max,maxn:longint;
    f:array[0..100000] of longint;
    g:array[0..100,1..2] of longint;
begin
  readln(n,v);
  for i:=1 to n do begin
    readln(g[i,1],g[i,2]);
    g[i,2]:=g[i,2]-g[i,1];
  end;
  for i:=1 to n do begin
    for j:=0 to v do begin
      if j-g[i,1]>=0 then begin
        if f[j-g[i,1]]+g[i,2]>f[j] then f[j]:=f[j-g[i,1]]+g[i,2];
      end;
    end;
  end;
  max:=0;
  for i:=0 to v do
      if f[i]+(v-i)>max then max:=f[i]+(v-i);
  writeln(max);
end.