#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll
using uint=unsigned;
using ull=unsigned ll;

#define gnr(i,a,b)for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define rng(i, a, b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) rng(i,0,n)
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
using vi=vc<int>;
#define a first
#define b second
#define mp make_pair
using vi=vc<int>;
#define pb push_back
#define eb emplace_back
template<class t,class u>bool chmax(t &a,u b){
	if(a <b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmin(t &a,u b){
	if(a>b){a=b;return true;}
	else return false;
}

#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>void mkuni(vc<t>&vs){
	sort(all(vs));
	vs.erase(unique(all(vs)),vs.ed);
}
template<class t>int lwb(const vc<t>&vs,t a){
	return lower_bound(all(vs),a)-vs.bg;
}

bool inc(int a,int b,int c){return a<=b&&b<=c;}

const int inf=INT_MAX/2-100;

using pi=pair<int,int>;

int getid(int h,int w){
	if(h<w)swap(h,w);
	return h*(h-1)/2+w-1;
}

const int smax=6;
const int S=smax*(smax+1)/2;

/*
vi ls[S];
void slv(){
	rng(h,1,smax+1)rng(w,1,h+1){
		int idx=getid(h,w);
		ls[idx].pb(1<<idx);
		//vert
		rng(i,1,h){
			int x=getid(i,w);
			int y=getid(h-i,w);
			for(auto u:ls[x])for(auto v:ls[y])
				ls[idx].pb(u^v);
		}
		//hori
		rng(i,1,w){
			int x=getid(h,i);
			int y=getid(h,w-i);
			for(auto u:ls[x])for(auto v:ls[y])
				ls[idx].pb(u^v);
		}
		mkuni(ls[idx]);
		cerr<<h<<" "<<w<<" "<<si(ls[idx])<<endl;
	}
}
*/

map<int,int> ls[S];

int readid(){
	string s;cin>>s;
	int res=getid(s[0]-'0',s[2]-'0');
	//cerr<<s<<" "<<res<<endl;
	return res;
}

void slv(){
	rng(h,1,smax+1)rng(w,1,h+1){
		int idx=getid(h,w);
		ls[idx][1<<idx]=0;
		//vert
		rng(i,1,h){
			int x=getid(i,w);
			int y=getid(h-i,w);
			for(auto u:ls[x])for(auto v:ls[y])
				if(ls[idx].find(u.a^v.a) != ls[idx].end()){
					chmin(ls[idx][(u.a^v.a)], u.b+v.b+1);
				}
				else ls[idx][u.a^v.a]=u.b+v.b+1;
		}
		//hori
		rng(i,1,w){
			int x=getid(h,i);
			int y=getid(h,w-i);
			for(auto u:ls[x])for(auto v:ls[y])
				if(ls[idx].find(u.a^v.a) != ls[idx].end()){
					chmin(ls[idx][(u.a^v.a)], u.b+v.b+1);
				}
				else ls[idx][u.a^v.a]=u.b+v.b+1;
		}
		//mkuni(ls[idx]);
		//cerr<<h<<" "<<w<<" "<<si(ls[idx])<<endl;
	}
	
	int n,t;cin>>n>>t;
	vi cnt(S);
	rep(i,n)cnt[readid()]++;
	vc<bool> ok(1<<S);
	{
		vi f(S);
		rng(h,1,smax+1)rng(w,1,h+1)f[getid(h,w)]=h*w;
		int tot=0;
		rep(i,S)tot+=f[i]*cnt[i];
		int cur=0;
		rep(bit,1<<S){
			//if(bit==1048578)cerr<<cur<<endl;
			if(tot-cur>=2*t)ok[bit]=true;
			rep(i,S)if(bit&1<<i){
				cur-=f[i];
			}else{
				cur+=f[i];
				break;
			}
		}
	}
	int ans=9;
	int ini=0;
	rep(i,S)if(cnt[i]%2)ini+=1<<i;
	//cerr<<ini<<" "<<ok[ini]<<endl;
	
	vc<pi> dp,nx;
	if(ok[ini])ans=0;
	else dp.eb(ini,0);
	
	per(i,S){
		per(_,min(cnt[i],6)){
			nx.clear();
			auto reach=[&](int bit,int v){
				if(ok[bit]){
					chmin(ans,v);
				}else if(v+1<ans){
					nx.eb(bit,v);
				}
			};
			for(auto [key,val]:dp)if(((ini^key)&1<<i)==0){
				for(auto [bit,cost]:ls[i]){
					reach(key^bit^(1<<i),val+cost);
				}
			}
			sort(all(nx));
			dp.clear();
			for(auto [key,val]:nx){
				if(val+1<ans){
					if(dp.empty()||dp.back().a!=key)dp.eb(key,val);
				}
			}
		}
		{
			nx.clear();
			for(auto [key,val]:dp){
				assert(!ok[key]);
				if(ok[(key>>i)<<i])nx.eb(key,val);
			}
			dp.swap(nx);
		}
	}
	cout<<ans<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	slv();
}