#include <stdio.h>#include <string.h>#define INF 1000000000#define LEN 90#define MAXN 10010char w[MAXN][LEN];int len[MAXN];int f[MAXN][LEN];bool visit[MAXN][LEN];int path[MAXN][LEN];int L,n;int input(){ int i,j,flag; char temp[MAXN]; gets(temp); sscanf(temp,"%d",&L); if(!L) return 0; n=1; while(1) { gets(temp); if(temp[0]==' ') break; for(flag=0,j=0,i=0; i<strlen(temp); i++) { if(temp[i]==' ' && !flag) continue; else if(temp[i]==' ' && flag) { flag=0; w[n][j]=' '; len[n]=strlen(w[n]); j=0; n++; } else if(temp[i]!=' ' && flag) w[n][j++]=temp[i]; else if(temp[i]!=' ' && !flag) { flag=1; j=0; w[n][j++]=temp[i]; } } if(flag) { w[n][j]=' '; len[n]=strlen(w[n]); n++; } } n--; return 1;}void print_path(int i , int j){ int t,k,c; if(i==n) { printf("%sn",w[i]); return ; } if(path[i][j]==0) { t=1; printf("%sn",w[i]); print_path(i+1,t); return ; } else if(path[i][j]!=-1) { c=path[i][j]; t=j+len[i]-1+c+1; printf("%s",w[i]); while(c) { printf(" "); c--;} print_path(i+1,t); return ; } return ;}int dp(int i , int j){ int ans,c,k,b; if(visit[i][j]) return f[i][j]; visit[i][j]=1; f[i][j]=INF; if(i>n) { if(j==1) return f[i][j]=0; else return f[i][j]=INF; } if( j+len[i]-1 == L) { ans=dp(i+1,1); if(ans<f[i][j]) { f[i][j]=ans; path[i][j]=0; } return f[i][j]; } if(j==1) { ans=dp(i+1,1)+500; if(ans<f[i][j]) { f[i][j]=ans; path[i][j]=0; } } c=j+len[i]-1+2; for(k=c; k<=L+1-len[i+1]; k++) { b=k-c; ans=dp(i+1,k)+b*b; if(ans<f[i][j]) { f[i][j]=ans; path[i][j]=b+1; } } return f[i][j];}void solve(){ int i,j; int ans; memset(path,-1,sizeof(path)); memset(visit,0,sizeof(visit)); len[n+1]=0; ans=dp(1,1); print_path(1,1); printf("n");}int main(){ while(input()) { solve(); } return 0;}
