/* 
 * File:   main.cpp
 * Author: Tibor
 *
 * Created on December 21, 2011, 3:13 PM
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

/*
 * 
 */
int num = 0, levagasosszeg = 0, *eredmeny;
string *adn;
int **levag;

bool foglalte(int n, int *elozmeny, int elem) {
    for (int i = 0; i < n; i++)
        if (elozmeny[i] == elem)return true;
    return false;
}

void keres(int n, int osszeg, int *elozmeny) {
    if (n >= num) {
        if (osszeg > levagasosszeg) {
            for (int i = 0; i < num; i++)
                eredmeny[i] = elozmeny[i];
            levagasosszeg = osszeg;
        }
    } else {
        for (int i = 0; i < num; i++)
            if (!foglalte(n, elozmeny, i)) {
                elozmeny[n] = i;
                if (n == 0)
                    keres(n + 1, osszeg, elozmeny);
                else
                    keres(n + 1, osszeg + levag[elozmeny[n - 1]][i], elozmeny);
            }
    }
}

int leveg(string e, string m) {
    int max = e.size() < m.size() ? e.size() : m.size();

    while (--max) {
        bool b = true;
        for (int i = 0; i <= max; i++) {
            if (e.at(e.size() - max + i - 1) != m.at(i)) {
                b = false;
                break;
            }
        }
        if (b) return max + 1;
    }
    return 0;
}

int main(int argc, char** argv) {
    string line;
    ifstream myfilein("adn.in");
    if (myfilein.is_open()) {
        if (myfilein.good()) {
            getline(myfilein, line);
            //            cout << line.c_str() << endl;
            num = atoi(line.c_str());
        }
        adn = new string[num];
        for (int i = 0; i < num; i++)
            if (myfilein.good()) {
                getline(myfilein, line);
                //                cout << line.c_str() << endl;
                adn[i] = line;
            }
        myfilein.close();
    } //else cout << "Unable to open file";

    for (int i = 0; i < num; i++)
        for (int j = 0; j < num; j++) {
            if (j == i || adn[i].empty() || adn[j].empty()) continue;

            if (adn[i].find(adn[j]) < 50)
                adn[j] = "";
        }

    //    cout << endl;

    int n = 0;
    for (int i = 0; i < num; i++)
        if (!adn[i].empty())n++;
    string adn2[n];
    n = 0;
    for (int i = 0; i < num; i++)
        if (!adn[i].empty())adn2[n++] = adn[i];
    adn = adn2;
    num = n;

    levag = new int*[num];
    for (int i = 0; i < num; i++) {
        levag[i] = new int[num];
        for (int j = 0; j < num; j++) {
            levag[i][j] = i != j ? leveg(adn[i], adn[j]) : 0;
        }
    }
    //    cout << "\n------------\n";
    //    for (int i = 0; i < num; i++) {
    //        cout << endl;
    //        for (int j = 0; j < num; j++) {
    //            cout << levag[i][j] << " ";
    //        }
    //    }

    //    cout << endl;
    eredmeny = new int[num];
    keres(0, 0, new int[num]);
    //    for (int i = 0; i < num; i++)
    //        cout << " " << eredmeny[i];
    //    cout << endl << levagasosszeg;
    //    cout << endl;

    //    for (int i = 0; i < num; i++)
    //        cout << i << adn[i] << endl;

    ofstream myfile;
    myfile.open("adn.out");
    char *c = new char[1000];
    myfile << adn[eredmeny[0]];
    for (int i = 1; i < num; i++) {
        for (int j = 0; j < 1000; j++)c[j] = 0;
        adn[eredmeny[i]].copy(c, adn[eredmeny[i]].size() - levag[eredmeny[i - 1]][eredmeny[i]], levag[eredmeny[i - 1]][eredmeny[i]]);
        myfile << c;
    }
    myfile.close();
    return 0;
}