#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb emplace_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int ty = 21;

int id[7][7];

bool ok[1 << ty];

//LL dp[1 << ty];
int dis[1 << ty];

int sz[ty];
vector<pair<int, int> > nxt[ty];

inline void init(int x, int y, int p)
{
	sz[p] = x * y;
	set<pair<int, int> > s0; 
	map<int, int> s1;
	REP(i, 1, (x >> 1) + 1)
	{
		s0.insert(mp(id[i][y], id[x - i][y]));
	}
	REP(i, 1, (y >> 1) + 1)
	{
		s0.insert(mp(id[x][i], id[x][y - i]));
	}
	for (auto u : s0) for (auto a : nxt[u.x]) for (auto b : nxt[u.y])
		if (s1.count(a.x ^ b.x)) chkmin(s1[a.x ^ b.x], a.y + b.y + 1);
		else s1[a.x ^ b.x] = a.y + b.y + 1;
	s1.insert(mp(1 << p, 0));
	for (auto u : s1) nxt[p].pb(u);
}

int vis[1 << ty];

const int maxn = 51;
pair<int, int> a[maxn + 5];

int nxtdis[1 << ty];

int need[1 << ty];

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	{
		int cnt = 0;
		REP(i, 1, 7)
			REP(j, 1, i + 1)
			{
				init(i, j, cnt);
				id[i][j] = id[j][i] = cnt++;
			}
		assert(cnt == ty);
	}
	int n, t;
	int sum = 0;
	scanf("%d%d", &n, &t);
	REP(i, 0, n)
	{
		int x, y;
		scanf("%dx%d", &x, &y);
		a[i] = mp(x, y);
		sum += x * y;
	}
	static int pos[ty];
	REP(i, 0, ty) pos[i] = i;
	sort(pos, pos + ty, [&](int x, int y) { return sz[x] < sz[y]; });
	t = sum - t * 2;
	REP(i, 0, 1 << ty) 
	{
		int s = 0;
		int cnt = 0;
		REP(j, 0, ty)
			if (i >> pos[j] & 1) 
			{
				s += sz[pos[j]];
				if (s > t) ++cnt;
			}
		need[i] = (cnt + 2) / 3;
		if (s <= t) ok[i] = 1;
		else ok[i] = 0;
	}
	memset(dis, oo, sizeof dis);
	int ans = 0;
	memset(vis, -1, sizeof vis);
	int tmp = 0;
	while (1)
	{
		vis[0] = tmp;
		dis[0] = 0;
		vector<int> cur, Nxt;
		cur.pb(0);
		REP(i, 0, n)
		{
			int rest = 0;
			REP(j, i, n)
			{
				rest ^= 1 << id[a[j].x][a[j].y];
			}
			Nxt.clear();
			for (auto u : cur)
			{
				if (dis[u] + need[u ^ rest] > ans) continue;
				for (auto v : nxt[id[a[i].x][a[i].y]]) 
				{
					if (dis[u] + v.y <= ans)
					{
						if (vis[u ^ v.x] != tmp)
						{
							vis[u ^ v.x] = tmp;
							Nxt.pb(u ^ v.x);
							nxtdis[u ^ v.x] = dis[u] + v.y;
						}
						else
						{
							chkmin(nxtdis[u ^ v.x], dis[u] + v.y);
						}
					}
				}
			}
			++tmp;
			cur = Nxt;
			for (auto u : cur) dis[u] = nxtdis[u];
		}
		bool found = 0;
		for (auto u : cur)
			if (ok[u])
			{
				found = 1;
			}
		if (found) break;
		++ans;
	}
	printf("%d\n", ans);
	return 0;
}