/*
TASK:lift
LANG:C
*/
#include<stdio.h>
 int a[16][2],n,t,m=30000,min1,min2,m2;
 char moved[16];

 void sort()
 {
  char p;
  int i,j;
  do{
   p=0;
   for(i=0;i<n-1;i++)
    if(a[i][0]>a[i+1][0] || (a[i][0]==a[i+1][0] && a[i][1]<a[i+1][1])){
    j=a[i][0]; a[i][0]=a[i+1][0]; a[i+1][0]=j;
    j=a[i][1]; a[i][1]=a[i+1][1]; a[i+1][1]=j;
    p=1;
    }
  }
  while(p);
  return;
 }

 void solve(int sum);

 int main()
 {
  int i,min=1000,max=0;
  scanf("%d %d",&n,&t);
  for(i=0;i<n;i++)
  {
   scanf("%d %d",&a[i][0],&a[i][1]);
   if(a[i][1]<min)min=a[i][1];
    else if(a[i][1]>max)max=a[i][1];
  }
  if(n==1){
   if(a[0][1]<=t)printf("%d\n",a[0][0]);
    else printf("0\n");
   return 0;
  }
  if(max+min>t){printf("0\n"); return 0;}
  sort();
  a[n][0]=a[n][1]=1000;
  solve(0);
  printf("%d\n",m-a[m2][0]);
  return 0;
 }

 void solve(int sum)
 {
  int i,j,w,g,k,min;
  //if(b==0)printf("%d\n",sum);
  i=n-1;
  while(i>=0 && moved[i])i--;
  j=i-1;
  while(j>=0 && moved[j])j--;
  if(j<=0 && i!=1){if(m>sum){m=sum;m2=min1;} return;}
  w=a[i][1]+a[0][1];
  j=i-1;
  if(j!=0){
   while(w<t && j>0){if(!moved[j])w+=a[j][1]; j--;}
   j++;
   if(!moved[j])w-=a[j][1];
  }
  sum+=a[i][0];
  for(g=j+1;g<=i;g++)moved[g]++;
  sum+=a[0][0]; min1=0;
  solve(sum);
  w-=a[n-1][0];
  min=t-w; min1=n; min2=n;
  for(g=1;g<j;g++)
   for(k=g+1;k<j;k++)
    if(min>a[g][1]+a[k][1] && !moved[g] && !moved[k])if(a[min1][0]+a[min2][0]>a[g][0]+a[k][0]){min1=g; min2=k;}
  if(min1!=n && min2!=n){
   moved[min2]=1;
   solve(sum);
   moved[min2]=0;
  }
  for(g=j+1;g<=i;g++)moved[g]--;
 }
