#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
int cost[15][15];
int dp[(1<<15)][15];
int cnt[15];
vector <int> order;
int n;

void gogo(int mask,int idx)
{
    order.push_back(idx+1);
    if(__builtin_popcount(mask)==1)return ;
    for(int i = 0; i < n; i++)
    {
        if(!(mask&(1<<i)))continue;
        if(dp[mask^(1<<idx)][i]+cost[i+1][idx+1]==dp[mask][idx])
        {
            gogo(mask^(1<<idx),i);
            break;
        }
    }
}

int Resi(int N, int K, int* L, char** A, char* S)
{
    n=N;
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(i==j){cost[i][j]=L[i];continue;}
            cost[i][j]=L[j];
            for(int k = 1; k <= min(L[i],L[j]); k++)
            {
                bool flag = true;
                for(int a = L[i]-k+1; a <= L[i]; a++)
                {
                    for(int b = 1; b <= k; b++)
                    {
                        if(A[i][a]!=A[j][b])flag=false;
                    }
                }
                if(flag)cost[i][j]=L[j]-k;
                if(flag && k == L[j])cnt[j]++;
            }
        }
    }
    for(int i = 1; i <= N; i++)
    {
        if(cnt[i]>=2)return -1;
    }
    for(int mask = 0; mask < (1<<N); mask++)for(int i = 0; i < N; i++)dp[mask][i]=INF;
    for(int i = 0; i < N; i++)dp[0][i]=0;
    for(int mask = 1; mask < (1<<N); mask++)
    {
        for(int i = 0; i < N; i++)
        {
            if(!(mask&(1<<i)))continue;
            for(int j = 0; j < N; j++)
            {
                if(!(mask&(1<<j)))continue;
                dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][j]+cost[j+1][i+1]);
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < N; i++)ans=min(ans,dp[(1<<N)-1][i]);
    for(int i = 0; i < N; i++)
    {
        if(dp[(1<<N)-1][i]==ans)
        {
            gogo((1<<N)-1,i);
            break;
        }
    }
    reverse(order.begin(),order.end());
    string ret = "";
    for(int j = 1; j <= L[order[0]]; j++)
    {
        ret += A[order[0]][j];
    }
    for(int i = 1; i < order.size(); i++)
    {
        for(int j = cost[order[i-1]][order[i]]+1; j <= L[order[i]]; j++)ret += A[order[i]][j];
    }
    if(ret.length()==0)while(1);
    for(int j = 0; j < ret.length(); j++)S[j+1]=ret[j];
    return ans;
}