/*
TASK:lift
LANG:C++
*/

#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

short N, T, h[15], w[15];
long shpCnt, ships[(1<<15)+1][2];

class mcmp
{
  public:
  const bool operator()(const pair<long, unsigned long> &a, const pair<long, unsigned long> &b) const
  {
    return a.first>b.first;
  }
};

long dij(void)
{
  char used[(1<<16)+1];
  unsigned long x, i;
  long dist[(1<<16)+1];
  priority_queue<pair<long, unsigned long>, vector<pair<long, unsigned long> >,  mcmp> pq;
  memset(used, 0, sizeof used);
  pq.push(make_pair(0, (1<<N)-1));
  while(!pq.empty() && !used[(1<<(N+1))-1])
  {
    x=pq.top().second;
    dist[x]=pq.top().first;
    used[x]=1;
    pq.pop();
    for(i=0; i<shpCnt; ++i)
      if(!((x|ships[i][0])^x) && !used[(x^((1<<(N+1))-1))|ships[i][0]])
        pq.push(make_pair(dist[x]+ships[i][1], (x^((1<<(N+1))-1))|ships[i][0]));
    while(!pq.empty() && used[pq.top().second])
      pq.pop();
  }
  if(used[(1<<(N+1))-1])
    return dist[(1<<(N+1))-1];
  return 0;
}

void input(void)
{
  short i;
  scanf("%hd %hd", &N, &T);
  for(i=0; i<N; ++i)
    scanf("%hd %hd", &h[i], &w[i]);
}

void calcShips(void)
{
  unsigned long i, j;
  short currW;
  for(shpCnt=0, i=1; i<(1<<N); ++i)
  {
    currW=0;
    ships[shpCnt][1]=0;
    for(j=0; j<N; ++j)
      if(i&(1<<j))
      {
        currW+=w[j];
        if(ships[shpCnt][1]<h[j])
          ships[shpCnt][1]=h[j];

      }
    if(currW<=T)
    {
      ships[shpCnt][0]=i;
      ++shpCnt;
    }
  }
}

int main(void)
{
  input();
  calcShips();
  printf("%ld\n", dij());
  return 0;
}

