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

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

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

vc<pi> ls[S];

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

using T=tuple<int,ull,int>;
void reduce(vc<T>&vs){
	sort(all(vs));
	int s=0;
	for(auto [bit,cnt,val]:vs){
		if(s==0||get<0>(vs[s-1])!=bit||get<1>(vs[s-1])!=cnt)
			vs[s++]=T(bit,cnt,val);
	}
	vs.resize(s);
}

ull mask(int i){
	return (ull(1)<<i)-1;
}

const int cmax=6;
void increment(ull&v,int i){
	int cur=(v>>(i*3))&7;
	int nx=min(cur+1,cmax);
	int dif=cur^nx;
	v^=ull(dif)<<(i*3);
}

void slv(){
	rng(h,1,smax+1)rng(w,1,h+1){
		int idx=getid(h,w);
		//vert
		rng(i,1,h){
			int x=getid(i,w);
			int y=getid(h-i,w);
			ls[idx].pb(minmax(x,y));
		}
		//hori
		rng(i,1,w){
			int x=getid(h,i);
			int y=getid(h,w-i);
			ls[idx].pb(minmax(x,y));
		}
		mkuni(ls[idx]);
	}
	
	int n,t;cin>>n>>t;
	vi rw(S);
	rep(i,n)rw[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]*rw[i];
		int cur=0;
		rep(bit,1<<S){
			if(tot-cur>=2*t)ok[bit]=true;
			rep(i,S)if(bit&1<<i){
				cur-=f[i];
			}else{
				cur+=f[i];
				break;
			}
		}
	}
	vi easy(1<<S,inf);
	rep(bit,1<<S){
		if(ok[bit])easy[bit]=0;
		else{
			rep(i,S)if(rw[i]>0||(bit&1<<i)){
				for(auto [x,y]:ls[i]){
					chmin(easy[bit],easy[bit^1<<i^1<<x^1<<y]+1);
				}
			}
		}
	}
	
	int ans=inf;
	
	int inibit=0;
	ull inicnt=0;
	rep(i,S){
		inicnt+=ull(min(rw[i],cmax))<<(i*3);
		if(rw[i]%2)inibit+=1<<i;
	}
	
	vc<T> dp[2][cmax+1];
	auto push=[&](int tar,int i,int bit,ull cnt,int val){
		if(ok[bit]){
			chmin(ans,val);
			return;
		}
		chmin(ans,val+easy[bit]);
		if(i==-1||val+1>=ans||!ok[bit>>(i+1)<<(i+1)])return;
		dp[tar][(cnt>>(i*3))&7].eb(bit,cnt&mask(i*3),val);
	};
	auto push2=[&](int tar,int i,int c,int bit,ull cnt,int val){
		if(ok[bit]){
			chmin(ans,val);
			return;
		}
		chmin(ans,val+easy[bit]);
		if(i==-1||val+1>=ans||!ok[bit>>(i+1)<<(i+1)])return;
		dp[tar][c].eb(bit,cnt&mask(i*3),val);
	};
	int cur=0;
	push(cur,S-1,inibit,inicnt,0);
	per(i,S){
		int nx=cur^1;
		rep(c,cmax+1)dp[nx][c].clear();
		per(c,cmax+1){
			reduce(dp[cur][c]);
			for(auto [bit,cnt,val]:dp[cur][c]){
				assert(cnt<(ull(1)<<(i*3)));
			}
			if(i>0){
				for(auto [bit,cnt,val]:dp[cur][c]){
					assert(!ok[bit]);
					push(nx,i-1,bit,cnt,val);
				}
			}
			if(c>0){
				for(auto [bit,cnt,val]:dp[cur][c]){
					for(auto [x,y]:ls[i]){
						int nxbit=bit^1<<i^1<<x^1<<y;
						ull nxcnt=cnt;
						increment(nxcnt,x);
						increment(nxcnt,y);
						push2(cur,i,c-1,nxbit,nxcnt,val+1);
					}
				}
			}
		}
		cur=nx;
	}
	
	cout<<ans<<endl;
}

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