#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
	for (auto elem : v) 
		stream << elem << " ";
	return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
		stream >> elem;
   return stream;
}

void settings() {
	#ifdef LOCAL
		freopen("io/input.txt", "r", stdin);
		freopen("io/output.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0);
	cin.tie(0);
}

vector<map<vi, int>> dp;
map<pii, int> mapper;
map<int, pii> invMapper;

int toMask(const vi& a) {
	int res = 0;
	for (int i = 0; i < a.size(); i++) res += (1LL<<i)*a[i];

	return res;
}

bool emp(const vi& a) {
	bool res = true;
	for (int i = 0; i < a.size(); i++)res &= a[i] == 0;
		return res;
}

int MAX_X = 2;
int res1 = -1;
int cnt = 0;

int currX = 0;

int getDP(int t, vi& a) {
	// if (res1 != -1) cnt++;
	// if (cnt >= 1000000) return INT_MAX;
	
	if (t <= 0) return 0;
	if (dp[t].count(a)) return dp[t][a];

	// if (res1 != -1 && currX >= res1) {
	// 	return INT_MAX;
	// }

	if (emp(a) && t > 0) return INT_MAX;

	int idx = 0;
	for (int i = 20; i >= 0; i--) {
		if (a[i] > 0) {
			idx = i;
			break;
		}
	}

	pii curr = invMapper[idx];

	vi oldA = a;
	for (int i = 0; i < 21; i++) {
		if (a[i] > MAX_X) {
			int tmp = a[i]-MAX_X;
			if (tmp % 2 == 1) tmp++;
			// cout << tmp << nL;
			a[i] -= tmp;
			dp[t][oldA] = getDP(t-invMapper[i].first*invMapper[i].second*(tmp/2), a);
			a[i] += tmp;
			return dp[t][oldA];
		}
	}

	int tmp = a[idx];
	a[idx] = 0;
	dp[t][oldA] = getDP(t-curr.first*curr.second*(tmp/2), a);
	a[idx] = tmp;

	for (int i = 1; i < curr.first; i++) {
		a[idx]--;
		a[(mapper[{i, curr.second}])]++;
		a[(mapper[{curr.first-i, curr.second}])]++;

		currX++;
		dp[t][oldA] = min(dp[t][oldA], getDP(t, a)+1);
		currX--;

		a[idx]++;
		a[(mapper[{i, curr.second}])]--;
		a[(mapper[{curr.first-i, curr.second}])]--;
	}

	for (int i = 1; i < curr.second; i++) {
		a[idx]--;

		a[(mapper[{curr.first, i}])]++;
		a[(mapper[{curr.first, curr.second-i}])]++;

		currX++;
		dp[t][oldA] = min(dp[t][oldA], getDP(t, a)+1);
		currX--;

		a[idx]++;

		a[(mapper[{curr.first, i}])]--;
		a[(mapper[{curr.first, curr.second-i}])]--;
	}

	return dp[t][oldA];
}

vector<map<vi, int>> dp2;
clock_t time_req;

int getDP2(int br, vi& a) {
	if ((float)(clock()- time_req)/CLOCKS_PER_SEC > 1.5) {
		return 0;
	}
	if (dp2[br].count(a)) return dp2[br][a];
	if (br == 0) {
		int tmp = 0;
		for (int i = 0; i < 21; i++) {
			tmp += (a[i]/2)*invMapper[i].first*invMapper[i].second;
		}
		dp2[br][a] = tmp;
		return tmp;
	}

	vi oldA = a;
	dp2[br][oldA] = getDP2(br-1, a);

	int idx = 0;
	for (int i = 20; i >= 0; i--) {
		if (a[i] > 0) {
			idx = i;
			break;
		}
	}

	int tmp = a[idx];
	a[idx] = 0;
	dp2[br][oldA] = getDP2(br, a)+(tmp/2)*invMapper[idx].first*invMapper[idx].second;
	a[idx] = tmp;

	pii curr = invMapper[idx];
	for (int i = 1; i < curr.first; i++) {
		a[idx]--;
		a[(mapper[{i, curr.second}])]++;
		a[(mapper[{curr.first-i, curr.second}])]++;

		dp2[br][oldA] = max(dp2[br][oldA], getDP2(br-1, a));

		a[idx]++;
		a[(mapper[{i, curr.second}])]--;
		a[(mapper[{curr.first-i, curr.second}])]--;
	}

	for (int i = 1; i < curr.second; i++) {
		a[idx]--;

		a[(mapper[{curr.first, i}])]++;
		a[(mapper[{curr.first, curr.second-i}])]++;
		
		dp2[br][oldA] = max(dp2[br][oldA], getDP2(br-1, a));
		// cout << curr.first << " " << curr.second << " " << dp[br][oldA] << nL;
		a[idx]++;

		a[(mapper[{curr.first, i}])]--;
		a[(mapper[{curr.first, curr.second-i}])]--;
	}

	return dp2[br][oldA];
}

signed main() {
	time_req = clock();

	int idx = 0;
	for (int i = 1; i <= 6; i++) {
		for (int j = i; j <= 6; j++) {
			mapper[{i, j}] = idx;
			invMapper[idx] = {i, j};
			mapper[{j, i}] = idx++;
		}
	}

	int n, t;
	cin >> n >> t;
	vi a(21);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		a[mapper[{s[0]-'0', s[2]-'0'}]]++;
	}

	// for (int i = 0; i < 21; i++) {
	// 	t -= invMapper[i].first*invMapper[i].second*(a[i]/2);
	// 	a[i] %= 2;
	// }
	// cout << a << nL;
	dp = vector<map<vi, int>>(t+5);

	MAX_X = 1;
	res1 = getDP(t, a);
	dp2 = vector<map<vi, int>>(res1+5);
	// MAX_X = 2;
	// cout << min(res1, getDP(t, a)) << nL;

	for (int i = 0; i <= res1; i++) {
		if ((float)(clock()- time_req)/CLOCKS_PER_SEC > 1.0) {
			cout << res1 << nL;
			break;
		}
		if (getDP2(i, a) < t) continue;
		cout << i << nL;
		break;
	}
	// cout << (float)(clock()- time_req)/CLOCKS_PER_SEC << nL;

	return 0;
}