gistfile1.txt

#include <iostream>
#include <set>
#include <string>
#include <vector>
#define optimizar ios_base::sync_with_stdio(0); cin.tie(0)
#define lld long long int
using namespace std;
const int MAXN = 100002;
const int LOG_N = 20;

int n;
string pal[13];

bool v[13][13];
int suf[13][13];
int suffixMax(int i, int j) {
    if(!i || !j) return 0; 
    if(v[i][j]) return suf[i][j];
    v[i][j] = true;
    int c = 0;
    for(int k = 0; k < pal[i].size(); k++) {
        if(k + pal[j].size() > pal[i].size()) {
            int sz = pal[i].size() - k;
            if(sz <= c) continue;
            if(pal[i].substr(k, sz) == pal[j].substr(0, sz)) c = sz;
        } else {
            int sz = pal[j].size();
            if(sz <= c) continue;
            if(pal[i].substr(k, sz) == pal[j]) c = sz;
        }
    }
    return suf[i][j] = c;
}

int dp[(1 << 14)][13];
int f(int msc, int last) {
    if(!msc) return 0;
    if(!dp[msc][last]) {
        dp[msc][last] = n * 50;
        for(int i = 0; i < n; i++) {
            if(msc & (1 << i)) {
                int x = suffixMax(last, i);
                if(x < pal[i].size()) dp[msc][last] = min(dp[msc][last], f(msc - (1 << i), i) + (int) pal[i].size() - x);
                else dp[msc][last] = min(dp[msc][last], f(msc - (1 << i), last));
            }
        }
    }
    return dp[msc][last];
}

string res;

void build() {
    int msc = (1 << n) - 1, last = -1;
    while(msc) {
        int sol = n * 50, newLast;
        string add = "";
        for(int i = 0; i < n; i++) {
            if(msc & (1 << i)) {
                int x = suffixMax(last, i);
                if(x < pal[i].size()) {
                    if(sol >= f(msc - (1 << i), i) + (int) pal[i].size() - x) {
                        if(sol == f(msc - (1 << i), i) + (int) pal[i].size() - x) {
                            if(x) {
                                if(add > pal[i].substr(x - 1, pal[i].size() - x)) {
                                    add = pal[i].substr(x - 1, pal[i].size() - x);
                                    newLast = i;
                                }
                            } else {
                                if(add > pal[i]) {
                                    add = pal[i];
                                    newLast = i;
                                }
                            }
                        } else {
                            if(x) add = pal[i].substr(x - 1, pal[i].size() - x);
                            else add = pal[i];
                            newLast = i;
                        }
                        sol = f(msc - (1 << i), i) + (int) pal[i].size() - x;
                    } 
                } else {
                    if(sol >= f(msc - (1 << i), last)) {
                        add = "";
                        newLast = i;
                        sol = f(msc - (1 << i), i) + (int) pal[i].size() - x;
                    }
                }
            }
        }
        res += add;
        last = newLast;
        msc -= (1 << last);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> pal[i];

    int r = n * 50;
    for(int i = 0; i < n; i++) {
        r = min(r, f((1 << n) - 1 - (1 << i), i) + (int) pal[i].size());
    }
    build();
    cout << res << "\n";
    return 0;
}