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

const int INF=1e9;

map<pair<int,int>,int> dict;
int mxid=0;
int id[10][10];
int sz[25];
pair<int,int> rec[25];
int w[(1<<21)+50];

int dfs(int mask,int W){
	if (W<=0) return 0;
	auto PAIR=make_pair(mask,W);
	if (dict.count(PAIR)!=0) return dict[PAIR];
	int ans=INF;
	
	{
		int top=31-__builtin_clz(mask);
		int nowx=rec[top].first;
		int nowy=rec[top].second;
		for (int x=1;x<=nowx-x;x++){
			int nxt=mask;
			nxt^=1<<top;
			nxt^=1<<id[x][nowy];
			nxt^=1<<id[nowx-x][nowy];
			ans=min(ans,dfs(nxt,W-w[mask]+w[nxt])+1);
		}
		for (int y=1;y<=nowy-y;y++){
			int nxt=mask;
			nxt^=1<<top;
			nxt^=1<<id[nowx][y];
			nxt^=1<<id[nowx][nowy-y];
			ans=min(ans,dfs(nxt,W-w[mask]+w[nxt])+1);
		}
	}
//	cerr << "mask,W,ans : " << bitset<21>(mask) << " " << W << " " << ans << "\n";
	return dict[PAIR]=ans;
}

int n,W;
int cnt[25];

int main(){
	ios_base::sync_with_stdio(false);
	
	mxid=0;
	for (int i=1;i<=6;i++){
		for (int j=i;j<=6;j++){
			id[i][j]=id[j][i]=mxid;
			sz[mxid]=i*j;
			rec[mxid]=make_pair(i,j);
			++mxid;	
		}
	}
	for (int mask=0;mask<(1<<mxid);mask++){
		for (int j=0;j<mxid;j++){
			if ((mask>>j)&1) w[mask]+=sz[j];
		}
	}
	/*
	cerr << "mxid : " << mxid << endl;
	for (int i=1;i<=6;i++){
		for (int j=1;j<=6;j++){
			cerr << id[i][j] << " ";	
		}
		cerr << endl;
	}
	*/
	cin >> n >> W;
	W<<=1;
	for (int i=1;i<=n;i++){
		int x,y;
		char ch;
		cin >> x >> ch >> y;
		cnt[id[x][y]]++;
	}
	for (int i=0;i<mxid;i++){
		W-=cnt[i]/2*2*sz[i];
		cnt[i]%=2;
	}
	{
		int now=0;
		for (int i=0;i<mxid;i++) now|=(cnt[i]<<i);
		cout << dfs(now,W) << "\n";	
	}
	return 0;	
}