#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 P=pair<int,int>;
using P1=pair<int,P>;

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

const int smax=6;
map<int,int>ls[smax*(smax+1)/2+1];

vc<P1>dp_cur, dp_nxt;
int buff[1<<21];
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, xx; cin >> n >> xx;
	dp_cur.eb(0, P(0, 0));
	int MAGIC=15000,sum=0;
	rep(i, n){
		string str; cin >> str;
		int a = str[0]-'0';
		int b = str[2]-'0';
		int id = getid(a, b);
		sum+=a*b;
		for(auto x:dp_cur){
			int val = x.a;
			int now = x.b.a;
			int orr = x.b.b;
			
			if(((orr>>id)&1)){
				dp_nxt.eb(val+0, P( (now^(1<<id)), (orr | (1<<id))));
				continue;
			}
			for(auto y:ls[id]){
				dp_nxt.eb(val+y.b, P( (now^y.a), (orr | y.a) ));
			}
		}
		sort(dp_nxt.begin(), dp_nxt.end());
		swap(dp_cur, dp_nxt);
		dp_nxt.clear();
		if((int)dp_cur.size()>MAGIC) dp_cur.resize(MAGIC);
		reverse(dp_cur.begin(), dp_cur.end());
	}
	int ans = 1e9;
	for(auto a:dp_cur){
		int val = a.a;
		int now = a.b.a;
		int S = sum;
		rng(h,1,smax+1)rng(w,1,h+1){
			int idx=getid(h,w);
			if(((now>>idx)&1)){
				S -= h*w;
			}
		}
		//if(S&1)cout<<S<<" "<<sum<<" "<<now<<endl;
		if(S >= 2*xx){
			chmin(ans, val);
		}
	}
	cout<<ans<<endl;
}

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