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

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>

const int MAXN = 14;
const int MAXC = 1 << MAXN;
const int INF = 1 << 29;

int N, T;
int _h[MAXN], _w[MAXN];
int h[MAXN], w[MAXN];
int ALL, NN;

std::vector <std::pair <int, int> > gr[MAXC * 2];

void rec (int pos, int mask, int maxh, int totw, int crnt_in) {
	if (pos == N) {
		if (crnt_in) gr[mask].push_back (std::make_pair (((~mask | crnt_in) & ALL) + NN, maxh));
		return;
	}
	rec (pos + 1, mask, maxh, totw, crnt_in);
	if ((mask >> pos) & 1)
		if (totw + w[pos] <= T)
			rec (pos + 1, mask, h[pos], totw + w[pos], crnt_in | (1 << pos));
}

int d[MAXC * 2];

void dijkstra () {
	static std::priority_queue <std::pair <int, int> > q;
	std::pair <int, int> c;
	q.push (std::make_pair (0, ALL));
	d[ALL] = 0;

	while (!q.empty ()) {
		c = q.top (); q.pop ();
		c.first *= -1;
//		printf ("popped (%d %d) %d\n", c.second % NN, c.second >= NN, c.first);
		if (d[c.second] < c.first) continue;//already popped

		for (size_t i = 0; i < gr[c.second].size (); ++i)
		    if (d[gr[c.second][i].first] > c.first + gr[c.second][i].second) {
                d[gr[c.second][i].first] = c.first + gr[c.second][i].second;
                q.push (std::make_pair (-d[gr[c.second][i].first], gr[c.second][i].first));
			}
	}
}

bool cmp (int a, int b) {return _h[a] < _h[b];}

int main () {
	scanf ("%d%d", &N, &T);
	NN = 1 << N;
	ALL = NN - 1;
	int i, j;
	static int idx[MAXN];
	for (i = 0; i < N; ++i) {
		scanf ("%d %d", _h + i, _w + i);
		idx[i] = i;
	}

	std::sort (idx, idx + N, cmp);
	for (i = 0; i < N; ++i) {h[i] = _h[idx[i]]; w[i] = _w[idx[i]];}
//	for (i = 0; i < N; ++i) printf ("%d %d\n", h[i], w[i]);
	for (i = 0; i < N; ++i) if (w[i] > T) {printf ("0\n"); return 0;}

	for (i = 0; i <= ALL; ++i) {
		rec (0, i, 0, 0, 0);

		for (j = 0; j < N; ++j)
		    if ((i >> j) & 1)
		        gr[i+NN].push_back (std::make_pair ((~i | 1 << j) & ALL, h[j]));
	}

/*	for (i = 0; i < NN; ++i) {
		printf ("%d ->", i);
		for (int j = 0; j < gr[i].size (); ++j)
		    printf (" (%d %d)", gr[i][j].first - NN, gr[i][j].second);
		printf ("\n");
	}
	for (i = 0; i < NN; ++i) {
		printf ("%d 1->", i);
		for (int j = 0; j < gr[i+NN].size (); ++j)
		    printf (" (%d %d)", gr[i+NN][j].first, gr[i+NN][j].second);
		printf ("\n");
	}*/

	std::fill (d, d + NN * 2, INF);
	dijkstra ();
	printf ("%d\n", d[NN+ALL] >= INF ? 0 : d[NN+ALL]);

	return 0;
}
