#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<int> nxt[ty];

inline void init(int x, int y, int p)
{
	sz[p] = x * y;
	set<int> s;
	REP(i, 1, x)
	{
		s.insert((1 << p) | (1 << id[i][y]) | (1 << id[x - i][y]));
	}
	REP(i, 1, y)
	{
		s.insert((1 << p) | (1 << id[x][i]) | (1 << id[x][y - i]));
	}
	for (auto u : s) nxt[p].pb(u);
}

int reachable[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);
	int initial = 0;
	REP(i, 0, n)
	{
		int x, y;
		scanf("%dx%d", &x, &y);
		sum += x * y;
		initial ^= 1 << id[x][y];
	}
	t = sum - t * 2;
	REP(i, 0, 1 << ty) 
	{
		int s = 0;
		REP(j, 0, ty)
			if (i >> j & 1) s += sz[j];
		if (s <= t) ok[i] = 1;
		else ok[i] = 0;
	}
	memset(dis, oo, sizeof dis);
	dis[initial] = 0;
	for (int i = ty - 1; i >= 0; --i)
	{
		REP(j, 0, 1 << ty)
			if ((j >> i & 1) && dis[j] < oo)
			{
				for (auto u : nxt[i])
					chkmin(dis[j ^ u], dis[j] + 1);
			}
	}
	int ans = oo;
	REP(i, 0, 1 << ty) if (ok[i]) 
	{
//		if (dis[i] < oo) debug("%d: %d\n", i, dis[i]);
		chkmin(ans, dis[i]);
	}
	printf("%d\n", ans);
	return 0;
}