A bit tricky problem, calculate the overlap, and then calculate if there are any substrings inside, substrings can be directly ignored.
Then take the remaining points to do the Hamilton Path with the minimum cost.
/\*
\* GCA : "Computer is artificial subject absolutely,Math is God"
\*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 25
#define PB push\_back
#define oo INT\_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
int n;
char str\[M\]\[M\];
int mz\[M\]\[M\];
int pnt\[M\];
bool nonused\[M\];
bool substr(int x,int y){
int xlen=strlen(str\[x\]);
int ylen=strlen(str\[y\]);
string sx(str\[x\]),sy(str\[y\]);
if(ylen>xlen)return false;
for(int i=0;i<=xlen-ylen;i++){
if(sx.substr(i,ylen)==sy)return true;
}
return false;
}
int count\_w(int x,int y){
int len=strlen(str\[x\]);
int len2=strlen(str\[y\]);
for(int i=max(0,len-len2);str\[x\]\[i\];i++){
bool suc=true;
int j,k;
for(j=i,k=0;str\[x\]\[j\]&&str\[y\]\[k\];j++,k++){
if(str\[x\]\[j\]!=str\[y\]\[k\]){
suc=false;
break;
}
}
if(suc)return k;
}
return 0;
}
int dp\[1<<15\]\[15\];
int dfs(int s,int now,int dep){
// debug("%d %d\\n",now,dep);
if(s==(1<<n)-1){
return 0;
}
if(dp\[s\]\[now\]!=-1)return dp\[s\]\[now\];
int minans=-1,t;
for(int i=0;i<n;i++){
if(i!=now&&!((s>>i)&1)){
int h;
if((h=dfs(s|(1<<i),i,dep+1))!=-1){
t=h+strlen(str\[pnt\[i\]\])-mz\[now\]\[i\];
}
if(minans==-1||t<minans){
minans=t;
}
}
}
return dp\[s\]\[now\]=minans;
}
void solve(){
Set(nonused,0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(substr(i,j))nonused\[j\]=1;
}
}
int cnt=0;
for(int i=0;i<n;i++){
if(!nonused\[i\])pnt\[cnt++\]=i;
}
n=cnt;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
mz\[i\]\[j\]=count\_w(pnt\[i\],pnt\[j\]);
// debug("%d %d %d\\n",i,j,mz\[i\]\[j\]);
}
}
Set(dp,-1);
int ans=oo;
// ans=dfs(1,0,0);
for(int i=0;i<n;i++){
int t=strlen(str\[pnt\[i\]\])+dfs(1<<i,i,0);
ans=min(ans,t);
}
printf("%d\\n",ans);
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;i++)scanf("%s",str\[i\]);
Set(mz,0);
solve();
}
}