{
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: byte;
 p,stubprice: word;
 newT: word;
 newH: byte;
begin
 if (lsideCt=0) then
 begin
  FindCheapest:=0;
  exit;
 end;

 p:=maxprice;
 newT:=stubT;
 for i:=1 to N do
 begin
  if left then
  begin
   if (lside[i].height=0) or (lside[i].weight+stubT>T) then
    continue;
  end
  else
   if (rside[i].height=0) or (rside[i].weight+stubT>T) then
    continue;

  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+lside[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 and (peopleCt=0) and (lsideCt>0) then
  begin
   stubprice:=FindCheapest(newT,newH,peopleCt+1,left);
   if stubprice<p then
    p:=stubprice;
  end
  else
  begin
   stubprice:=FindCheapest(0,0,0,not left)+newH;
   if stubprice<p then
    p:=stubprice;
   if left and (lsideCt>0) then
   begin
    stubprice:=FindCheapest(newT,newH,peopleCt+1,left);
    if stubprice<p then
     p:=stubprice;
   end;
  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;
 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.
