http://poj.org/problem?id=1093
#include<iostream>
using namespace std;
const char space=' ';
char word[10001],l;
int len[10002],m,n;
int jie[10002];
int chen[10002];
long bad[10002];
void init()
{int h=0,j=1,t=0;
while(cin.get())
{if(cin.peek()==10)break;
while(cin.peek()!=10)
{if(cin.peek()==32){cin.get();if(t){len[j++]=t;t=0;}}
else {cin.get(word[h++]);
t++;}
}
if(t){len[j++]=t;t=0;}
}
len[0]=0;
m=j-1;
l=h;
//for(i=0;i<l;i++)cout<<word[i];
//cout<<endl;
//for(i=1;i<=m;i++)cout<<len[i]<<endl;
}
long point(long n,long p)
{long j=p/n,s=0;
while(p%n)
{s+=(j+1)*(j+1);
p-=j+1;n--;
}
return s+(p/n)*(p/n)*n;
}
void doit()
{long s,p,j,i;
jie[0]=0;bad[0]=0;
jie[1]=1;bad[1]=500;
chen[0]=0;chen[1]=1;
for(i=2;i<=m;i++)
{bad[i]=500+bad[i-1];jie[i]=i;chen[i]=chen[i-1]+1;
s=len[i]+1+len[i-1];
for(j=i-1;s<=n&&j>0;j--)
{p=point(i-j,n-s)+bad[j-1];
if(p<bad[i]||(p==bad[i]&&chen[j-1]<chen[jie[i]-1])){bad[i]=p;jie[i]=j;chen[i]=chen[j-1]+1;}
if(j>1)s+=len[j-1]+1;
}
}
}
void print()
{int stack[10001],i,j,s,h;
for(i=m;i>0;i=jie[i]-1)
{s=0;
for(j=i;j>=jie[i];j--)
s+=len[j];s=n-s;
for(j=jie[i];j<i;j++)
{stack[j]=s/(i-j);s-=s/(i-j);}
stack[i]=-1;
}
stack[0]=-1;
h=0;
for(i=1;i<=m;i++)
{for(j=0;j<len[i];j++)cout<<word[h++];
//if(stack[i]==-1&&stack[i-1]==-1){for(j=0;j<n-len[i];j++)cout<<space;cout<<endl;}
if(stack[i]==-1)cout<<endl;
else for(j=0;j<stack[i];j++)cout<<space;
}
}
int main()
{while(1)
{cin>>n;if(n==0)break;
init();
doit();
print();
cout<<endl;
}
return 0;
}