{
TASK:lift
LANG:Pascal
}
program LIFT;

const
 maxN = 15;
 maxprice = 65000;

type
 man = record
  height: byte;
  weight: byte;
 end;

 people = array[1..maxN] of man;

var
 N,i: byte;
 T: word;
 lside,rside: people;
 lsideCt,rsideCt: byte;

procedure InitPeople(var p: people);
var
 i: byte;
begin
 for i:=1 to maxN do
 begin
  p[i].height:=0;
  p[i].weight:=0;
 end;
end;

function FindCheapest(stubT: word; maxH,peopleCt: byte; left: boolean): word;
var
 i,j,stubi: byte;
 p,stubprice: word;
 newT,stubW: word;
 newH,stubH: byte;
begin
 if (lsideCt=0) then
 begin
  FindCheapest:=maxH;
  exit;
 end;

 stubH:=0;
 stubW:=200;
 stubi:=0;
 if left and (peopleCt>0) then
 begin
  stubH:=maxH;
  stubW:=0;
  for i:=1 to N do
  begin
   if (lside[i].height=0) or (lside[i].weight+stubT>T) then
    continue;

   if (lside[i].height<stubH) or
      ((lside[i].height=stubH) and (lside[i].weight>stubW)) then
   begin
    stubi:=i;
    stubH:=lside[i].height;
    stubW:=lside[i].weight;
   end;
  end;
 end
 else
  if left then
   for i:=1 to N do
   begin
    if (lside[i].height=0) or (lside[i].weight+stubT>T) then
     continue;

    if (lside[i].height>stubH) or
       ((lside[i].height=stubH) and (lside[i].weight<stubW)) then
    begin
     stubi:=i;
     stubH:=lside[i].height;
     stubW:=lside[i].weight;
    end;
   end
  else
  begin
   stubH:=250;
   stubW:=200;
   for i:=1 to N do
   begin
    if (rside[i].height=0) or (rside[i].weight+stubT>T) then
     continue;

      if (rside[i].height<stubH) or
       ((lside[i].height=stubH) and (rside[i].weight<stubW)) then
    begin
     stubi:=i;
     stubH:=rside[i].height;
     stubW:=rside[i].weight;
    end;
   end;
  end;

 p:=maxprice;
 if (stubi=0) then
 begin
  FindCheapest:=p;
  exit;
 end;

 i:=stubi;
 newH:=maxH;
 for j:=1 to N do
  if left then
  begin
   if rside[j].height>0 then
    continue;

   newT:=stubT+lside[i].weight;
   if maxH<lside[i].height then
    newH:=lside[i].height;
   rside[j].height:=lside[i].height;
   rside[j].weight:=lside[i].weight;
   lside[i].height:=0;
   rsideCt:=rsideCt+1;
   lsideCt:=lsideCt-1;
   break;
  end
  else
  begin
   if lside[j].height>0 then
    continue;

   newT:=stubT+rside[i].weight;
   if maxH<rside[i].height then
    newH:=rside[i].height;
   lside[j].height:=rside[i].height;
   lside[j].weight:=rside[i].weight;
   rside[i].height:=0;
   lsideCt:=lsideCt+1;
   rsideCt:=rsideCt-1;
   break;
  end;

 if left then
 begin
  stubprice:=FindCheapest(newT,newH,peopleCt+1,true);
  if stubprice=maxprice then
   if peopleCt=0 then
    exit
   else
    stubprice:=FindCheapest(0,0,0,false)+newH;
  if stubprice<p then
   p:=stubprice;
 end
 else
 begin
  stubprice:=FindCheapest(0,0,0,true)+newH;
  if stubprice<p then
   p:=stubprice;
 end;

 if left then
 begin
  lside[i].height:=rside[j].height;
  lside[i].weight:=rside[j].weight;
  rside[j].height:=0;
  lsideCt:=lsideCt+1;
  rsideCt:=rsideCt-1;
 end
 else
 begin
  rside[i].height:=lside[j].height;
  rside[i].weight:=lside[j].weight;
  lside[j].height:=0;
  rsideCt:=rsideCt+1;
  lsideCt:=lsideCt-1;
 end;

 FindCheapest:=p;
end;

begin
 InitPeople(lside);
 InitPeople(rside);
 readln(N,T);
 for i:=1 to N do
  readln(lside[i].height,lside[i].weight);
 lsideCt:=N;
 rsideCt:=0;
 writeln(FindCheapest(0,0,0,true));
end.
