//start of jonathanirvings' template v3.0.3 (BETA)

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

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

vector<string> split_string(string);

int dp[1<<19][19];
bool ok[1<<19];
int ada[20][10];
int b[20];
int n;
vi mati[1<<19];

int jahja(int last,int mask)
{
    if (!ok[mask]) return -INF;
    if (mask == (1<<n)-1) return 0;
    int &ret = dp[mask][last];
    if (ret != -1) return ret;
    ret = 0;
    for (int i : mati[mask])
    {
        MAX(ret,jahja(i,mask | (1 << i)) + (b[last] ^ b[i]));
    }
    return ret;
}

// Complete the maximumElegance function below.
int maximumElegance(int q, vector<string> s, vector<int> _b) {
    // Return an integer denoting the maximum elegance which can be obtained by Diane.
    n = SIZE(_b);
    REP(i,1<<n)
    {
        REP(j,n)
        {
            if (i & (1 << j)) continue;
            mati[i].pb(j);
        }
    }
    REP(i,n)
    {
        REP(j,SIZE(s[i])) ++ada[i][s[i][j] - '0'];
    }
    REP(i,1<<n)
    {
        vi pakai(10);
        REP(j,n)
        {
            if (i & (1 << j))
            {
                REP(k,10) pakai[k] += ada[j][k];
            }
        }
        ok[i] = 1;
        REP(k,10) if(pakai[k] > q) ok[i] = 0;
    }
    REP(i,n) b[i] = _b[i];
    RESET(dp,-1);
    int risan = 0;
    REP(i,n)
    {
        vi sisa = vector<int>(10, q);
        REP(j,10)
        {
            if (sisa[j] < ada[i][j]) goto hell;
            sisa[j] -= ada[i][j];
        }
        MAX(risan,jahja(i,1<<i) + b[i]);
        hell:;
    }
    return risan;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nq_temp;
    getline(cin, nq_temp);

    vector<string> nq = split_string(nq_temp);

    int n = stoi(nq[0]);

    int q = stoi(nq[1]);

    string b_temp_temp;
    getline(cin, b_temp_temp);

    vector<string> b_temp = split_string(b_temp_temp);

    vector<int> b(n);

    for (int i = 0; i < n; i++) {
        int b_item = stoi(b_temp[i]);

        b[i] = b_item;
    }

    vector<string> s(n);

    for (int i = 0; i < n; i++) {
        string s_item;
        getline(cin, s_item);

        s[i] = s_item;
    }

    int result = maximumElegance(q, s, b);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}