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

#include <cstdio>
#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;

int dp[MAXC][2];

int dpf (int, bool);
int _cres[MAXC];

void rec (int pos, int mask, int maxh, int totw, int crnt_in) {
//	printf ("rec %d, %d %d %d %x\n", pos, mask, maxh, totw, crnt_in);
	if (pos == N) {
//		printf ("\t%x\n", (~mask | crnt_in) & ALL);
		if (crnt_in) _cres[mask] <?= dpf ((~mask | crnt_in) & ALL, 1) + 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 dpf (int id, bool side) {
//	printf ("RAWdpf %d %d\n", id, side);
	if (dp[id][side] != -1) return dp[id][side];
//	printf ("dpf %d %d\n", id, side);
	int cres = dp[id][side] = INF;//if there is a cycle in the recursion - it will return INF
	if (side) {
		for (int i = 0; i < N; ++i)
		    if ((id >> i) & 1)
				cres <?= dpf ((~id | (1 << i)) & ALL, 0) + h[i];
	} else {
		rec (0, id, 0, 0, 0);
		cres = _cres[id];
	}

//	printf ("<--%d %d    %d\n", id, side, cres);
	return dp[id][side] = cres;
}

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

int main () {
	scanf ("%d%d", &N, &T);
	ALL = (1 << N) - 1;
	int i;
	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]);
	memset (dp, -1, sizeof (dp));
	for (i = 0; i <= ALL; ++i) _cres[i] = INF;
	dp[ALL][1] = 0;//the final situation
	dpf (ALL, 0);

	printf ("%d\n", dp[ALL][0]);

	return 0;
}
