/*
TASK:lift
LANG:C++
*/
#include<stdio.h>
#define maxn 15
#define max2 17000
#define lowbit(x) (((x) & ((x)-1))^(x))

#define MAX(a, b) (((a)<(b))?(b):(a))
#define MIN(a, b) (((a)<(b))?(a):(b))


using namespace std;
void input();
void solve();


int N, T;
int t[maxn], w[maxn];
int weight[max2], height[max2];
int log2[max2];
int valid[max2]; int top = 0;
int dp[max2];


int ALL_BITS;


int main()
{
input();
solve();
return 0;
}



void solve()
{
int i, j, x;
int A, B, C;
weight[0] = height[0] = 0;


for(i = 1; i < (1<<N); i++)
	{
	weight[i] = weight[i-lowbit(i)] + w[log2[lowbit(i)]];
	height[i] = MAX(height[i-lowbit(i)] , t[log2[lowbit(i)]]);
	if(weight[i] <= T) valid[top++] = i;
	}
ALL_BITS = (1<<N) - 1; //superset
for(i = 0; i < N; i++) if(w[i] > T) { printf("0\n"); return; } // There is a person who cannot fit in the lift

dp[0] = 0;
for(A = 1; A < (1<<N); A++) 			//A is a set that we want to transport
	{
	dp[A] = 1000000000;

	C = (ALL_BITS^A);			//C is the set of people already there (A's negation)

	for(j = 0; j < top; j++)
		{
		B = valid[j];			//B is a valid transportable set

		if(B == A) { dp[A] = height[A]; continue; } //if B coincides with A

		if((A & B) == B)		//else if B is a subset of A
			{
			for(int x = 1; x < (1<<N); x += x)
				if(x & B)		//log2[x] is a person in set B
					{
					int cost = height[B] + t[log2[x]] + dp[A-B + x];
					dp[A] = MIN(dp[A], cost);
					}
			}
		}
	}

if(dp[ALL_BITS] >= 1000000000) printf("0\n");
else printf("%d\n", dp[ALL_BITS]);
}



void input()
{
scanf("%d%d", &N, &T);
for(int i = 0; i < N; i++) scanf("%d%d", &t[i], &w[i]);

log2[1] = 0;
for(int i = 2; i <= (1<<N); i += i) log2[i] = log2[i/2] + 1;
}

