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

const int INF=1e9;
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 n,W;
int x[55],y[55];
int sum[55];
vector<pair<int,int>> v[25];
int dp[25][(1<<21)+50];

int dfs(int dep,int mask){
	cerr << "dfs:" << dep << " " << mask << endl;
	if (sum[dep-1]-w[mask]>=W) return 0;
	if (dep==n+1) return INF;
	
	auto PAIR=make_pair(dep,mask);
	if (dict.count(PAIR)!=0) return dict[PAIR];
	int ans=INF;
	
	{
		int nowid=id[x[dep]][y[dep]];
		for (auto [m1,s1]:v[nowid]) ans=min(ans,dfs(dep+1,mask^m1)+s1); 
	}
	
	return dict[PAIR]=ans;
}

int f[1<<21][2];
int g[2][1<<22],gc[1<<22],gn[2];

int p[55];
inline bool cmp(const int k1,const int k2){ return id[x[k1]][y[k1]] < id[x[k2]][y[k2]]; }

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];
		}
	}
	
	for (int i=1;i<=6;i++){
		for (int j=i;j<=6;j++){
		//	cerr << i << " " << j << endl;
			for (int mask=0;mask<(1<<mxid);mask++) dp[id[i][j]][mask]=INF;
			dp[id[i][j]][1<<id[i][j]]=0;
			
			for (int k=1;k<=i-k;k++){
				int id1=id[k][j];
				int id2=id[i-k][j];
				for (auto [m1,s1]:v[id1]){
					for (auto [m2,s2]:v[id2]){
						dp[id[i][j]][m1^m2]=min(dp[id[i][j]][m1^m2],s1+s2+1);
					}
				}
			}
			for (int l=1;l<=j-l;l++){
				int id1=id[i][l];
				int id2=id[i][j-l];
				for (auto [m1,s1]:v[id1]){
					for (auto [m2,s2]:v[id2]){
						dp[id[i][j]][m1^m2]=min(dp[id[i][j]][m1^m2],s1+s2+1);
					}
				}	
			}
			for (int mask=0;mask<(1<<mxid);mask++) if (dp[id[i][j]][mask]!=INF){
			//	if (__builtin_popcount(mask)>6) continue;
				v[id[i][j]].emplace_back(mask,dp[id[i][j]][mask]);	
			}
		//	cerr << i << " " << j << endl;
		//	cerr << v[id[i][j]].size() << endl;
		}
	}
	
	cin >> n >> W;
	W<<=1;
	for (int i=1;i<=n;i++){
		char ch;
		cin >> x[i] >> ch >> y[i];	
	}
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+n+1,cmp);
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+x[p[i]]*y[p[i]];
	
	
	int ans=inf;
	memset(g,0,sizeof g);
	memset(f,-1,sizeof f);
	int now=0;
	g[now][++gn[now]]=0; f[0][0]=0,f[0][1]=0;
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=gn[now];j++)
		{
			int s=g[now][j];
			if(i==n+1 && s==0)
				int kk=1;
			gc[j]=f[s][1];
			if(f[s][1]<ans)
			{
				int temp=sum[i-1];
				for(int k=1;k<=mxid;k++) if(s>>(k-1)&1)
					temp-=sz[k];
				
				if(i==n+1)
				{
					int kk=1;
				}
				if(temp>=W) 
				{
					ans=min(ans,f[s][1]);
				}
			}
		}
		
		if(i==n+1) break;
		now=!now; gn[now]=0;
		for(int j=1;j<=gn[!now];j++)
		{
			int s=g[!now][j];
			int c=gc[j];
			
			if(s==2114)
				int kk=1;
			
			for(auto [si,ci]:v[id[x[p[i]]][y[p[i]]]])
			{
				int ns=s^si;
				if(i==n && ns==0)
					int kk=1;
				if(f[ns][0]!=i || f[ns][1]>c+ci)
				{
					if(s==2114 && si==2114 && ns==0)
						int kk=1;
					f[ns][1]=c+ci;
					if(f[ns][0]!=i)
					{
						f[ns][0]=i;
						g[now][++gn[now]]=ns;
					}
				}
			}
		}
	}
	
	cout << ans << "\n";
	
	return 0;	
}