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

#include <stdio.h>
#include <queue>
using namespace std;

#define min(a,b) ((a)<(b) ? (a):(b))
#define max(a,b) ((a)>(b) ? (a):(b))

struct vertex {
	int mask;
	bool lift;
	int cost;

	vertex () {}
	vertex (int _mask, bool _lift, int _cost) : mask(_mask), lift(_lift), cost(_cost) {}
};

bool operator< (const vertex &a, const vertex &b) { return a.cost<b.cost; }

const int MAX_N = 15;
const int INF   = 1000000000;

int n, T;
int H[MAX_N];
int W[MAX_N];
priority_queue<vertex> Q;

int dp[1<<15][2];

void input ()
{
	int i;

	scanf ("%d%d", &n, &T);

	for (i=0; i<n; i++)
		scanf ("%d%d", &H[i], &W[i]);
}

void solve ()
{
	int i, j, get, get2, curr_w, curr_h, m;
	vertex curr, next;

	for (i=0; i<(1<<n); i++)
		dp[i][0] = dp[i][1] = INF;

	Q.push ( vertex(0,0,0) );


	while (!Q.empty()) {
		curr = Q.top(); Q.pop();
		dp[curr.mask][curr.lift] = curr.cost;
		if (curr.cost > dp[(1<<n)-1][1]) continue;
		
		for (m=0, i=curr.mask; i; i>>=1) if (i&1) m++;
		if (curr.lift == 0) m=n-m;

		for (get=1; get<(1<<m); get++) {
			curr_w = 0;
			curr_h = 0;

			get2=0;
			j=0;

			for (i=0; i<n; i++) {
				if ( ((curr.mask>>i)&1) == curr.lift ) {
					if ((get>>j)&1) {
						curr_w += W[i];
						curr_h = max( curr_h, H[i] );
						get2 |= (1<<i);
					}

					j++;
				}
			}

			if (curr_w <= T) {
				next = vertex(curr.mask^get2, !curr.lift, curr.cost+curr_h); 
				//printf ("mask: %d   lift: %d   cost: %d\n", next.mask, next.lift, next.cost);
				if (next.cost < dp[next.mask][next.lift]) {
					Q.push( next );
				}
			}
		}
	}
}

int main ()
{
	//freopen ("lift2.in", "r", stdin);
	//freopen ("lift.out", "w", stdout);

	input ();
	solve ();

	printf ("%d\n", dp[(1<<n)-1][1]!=INF ? dp[(1<<n)-1][1] : 0);

	return 0;
}