#include <stdio.h>
#include <stdlib.h>
#define DM (20)
#define N (1<<DM)
#define D (6)
#define ANT (D*(D-1)/2+D)
#define INF (1<<30)
#define MAXN (50)
#define MAX_BREAK (3)

void hadamard(int* v)
{
  int i,j,k;
  for (i=0;i<DM;i++) {
    int spc=(1<<i);
    for (j=0;j<N;j+=2*spc) {
      for (k=0;k<spc;k++) {
        int a=v[j+k];
        int b=v[j+k+spc];
        v[j+k]=a+b;
        v[j+k+spc]=a-b; 
      }
    }
  }
}


int v[N];
int id[(D+1)*(D+1)];

int adj[ANT][3000][2];
int nadj[ANT];
int set[2*N];
int bar[MAXN];
unsigned char dp[2][N];
int sz[ANT];
int par=0;
int tot=0;

int main()
{
  int i,j,k,l,m;
  char r[8];
  int n,t;
  int nid=0;
  int best=INF;
  for (i=1;i<=D;i++) {
    for (j=i;j<=D;j++) {
      id[i*(D+1)+j]=nid;
      id[j*(D+1)+i]=nid;
      nadj[nid]=0;
      sz[nid]=i*j;
      nid++;
    }
  }
  int c=0;
  scanf("%d %d",&n,&t);
  while (scanf("%s",r)==1) {
    int a=(int)(r[0])-(int)'0';
    int b=(int)(r[2])-(int)'0';
    //printf("%d %d\n",a,b);
    par^=((a*b)&1);
    tot+=a*b;
    bar[c++]=id[a*(D+1)+b]; 
  }
  
  for (i=0;i<ANT;i++) {
    adj[i][0][0]=(1<<i);
    adj[i][0][1]=0;
    nadj[i]=1;
  }
  for (i=1;i<=D;i++) {
    for (j=i;j<=D;j++) {
      for (k=0;k<2*N;k++) set[k]=INF;
      for (k=1;k<i;k++) {
        for (l=0;l<nadj[id[k*(D+1)+j]];l++) {
          int f1 = adj[id[k*(D+1)+j]][l][0];
          int c1 = adj[id[k*(D+1)+j]][l][1];
          
          for (m=0;m<nadj[id[(i-k)*(D+1)+j]];m++) {
            int f2 = adj[id[(i-k)*(D+1)+j]][m][0];
            int c2 = adj[id[(i-k)*(D+1)+j]][m][1];
            if (c1+c2+1<MAX_BREAK && c1+c2+1 < set[f1^f2]) set[f1^f2] = c1+c2+1;
          }
        }
      }
      if (i!=j) {
        for (k=1;k<j;k++) {
          //adj[id[i*(D+1)+j]][nadj[id[i*(D+1)+j]]++]=(id[i*(D+1)+k]<<10)|(id[i*(D+1)+j-k]);
          for (l=0;l<nadj[id[i*(D+1)+k]];l++) {
            int f1 = adj[id[i*(D+1)+k]][l][0];
            int c1 = adj[id[i*(D+1)+k]][l][1];
          
            for (m=0;m<nadj[id[i*(D+1)+j-k]];m++) {
              int f2 = adj[id[i*(D+1)+j-k]][m][0];
              int c2 = adj[id[i*(D+1)+j-k]][m][1];
              if (c1+c2+1<MAX_BREAK && c1+c2+1 < set[f1^f2]) set[f1^f2] = c1+c2+1;
            }
          }   
        }        
      }
      for (k=0;k<2*N;k++) 
        if (set[k]<INF) {
          adj[id[i*(D+1)+j]][nadj[id[i*(D+1)+j]]][0] = k;
          adj[id[i*(D+1)+j]][nadj[id[i*(D+1)+j]]][1] = set[k]; 
          nadj[id[i*(D+1)+j]]++;      
        }  
    }
  }  
  /*
  for (i=0;i<ANT;i++)
    printf("%d: %d\n",i,nadj[i]);
  */
  for (i=0;i<N;i++) dp[0][i]=128;
  dp[0][0]=0;
  
  for (i=0;i<n;i++) {
    for (j=0;j<N;j++) dp[(i+1)&1][j]=128;
    
    for (j=0;j<nadj[bar[i]];j++) {
      int b=adj[bar[i]][j][0]>>1;
      int c=adj[bar[i]][j][1];
      for (k=0;k<N;k++) {
        if (dp[i&1][k^b]+c<dp[(i+1)&1][k])
          dp[(i+1)&1][k]=dp[i&1][k^b]+c;
      }
    }
  }
  
  for (i=0;i<N;i++)
    if (dp[n&1][i]<best) {
      int sm=0;
      for (j=0;j<ANT-1;j++)
        if ((i>>j)&1)
          sm+=sz[j+1];
      if ((sm&1)!=par)
        sm+=sz[0]; 
      if (tot-sm>=2*t)
        best=dp[n&1][i];    
    }
  printf("%d\n",best); //dp[n&1][0]);
  return 0;
}