/* 
 * 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();
    int n = 0, ret = 0;
    while (n < max) {
        bool b = true;
        for (int i = 0; i <= n; i++) {
            if (e.at(e.size() - n + i - 1) != m.at(i)) {
                b = false;
                break;
            }
        }

        n++;
        if (b)
            ret = n;
    }
    return ret;
}

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[100]="alma";
        myfile<< adn[eredmeny[0]];
    for(int i=1;i<num;i++){
        for(int j=0;j<100;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;
}