/*
TASK:lift
LANG:C
*/
#include <stdio.h>
#define MAXN 16
#define MAXW 33000
#define min(a, b) (a<b?a:b)
#define max(a, b) (a>b?a:b)
#define getT(i, sit) ((sit&(1<<i))>>i)
#define PLUSINF 1000000000
struct turisti{
    int h, w;
}tur[MAXN];
long int counted[MAXW][2];
long int count(int sit, int lift);

int N, T;
main()
{
    int i;
    for(i=0; i<MAXW; i++)
        counted[i][0] = counted[i][1] = -1;
    scanf("%d %d", &N, &T);
    for(i=0; i<N; i++)
        scanf("%d %d", &tur[i].h, &tur[i].w);
    
    i = count(0, 0);
    printf("%d\n", i==PLUSINF?0:i);
    return 0;
}

long int count(int sit, int lift)
{
    int in[MAXN], ways, i, a, ret=PLUSINF, wigh, high;
    if(counted[sit][lift]!=-1)
        return counted[sit][lift];
    if(sit==((1<<N) - 1) && lift)
        return 0;
      //bez povtorenia
    counted[sit][lift] = PLUSINF;
    
    ways = CountWay(sit, lift, in);
    for(i = 0; i < (1<<ways); i++)
    {
        wigh = getwigh(lift, in, ways, i);
        if(wigh<T && wigh>0)
        {
            high = gethigh(lift, in, ways, i);
            a = count(makesit(sit, in, ways, i), lift?0:1) + high;
            ret = min(a, ret);
        }
    }
    counted[sit][lift] = ret;
    return ret;
}
    
int CountWay(int sit, int lift, int in[])
{
    int i, ret=0;
    for(i=0; i<N; i++)
        if(getT(i, sit) == lift)
            in[ret++] = i;
    return ret;
}

int makesit(int sit, int in[], int ways, int mask)
{
    int ret=sit, y=0, b;
    for(y=0; y<ways; y++)
    {
        b = getT(y, mask);
        ret = ((ret & (((1<<N)-1)-(1<<in[y]))) | (b<<in[y]));
    }
    return ret;
}

int getwigh(int lift, int in[], int ways, int mask)
{
    int i, ret=0;
    for(i=0; i<ways; i++)
        if(getT(i, mask) != lift)
            ret+=tur[N-1-in[i]].w;
    return ret;
}
int gethigh(int lift, int in[], int ways, int mask)
{
    int i, ret=0;
    for(i=0; i<ways; i++)
        if(getT(i, mask) != lift)
            ret = max(ret, tur[N-1-in[i]].h);
    return ret;
}
