#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <ctype.h>


#if 0
#undef assert
#define assert(x)
#endif

#define xDEBUG 1
#define xDEBUGG 1

static int F[20000],FN;
static int Best[20000];

int Width;

static int lineeval(int start,int len)
{
int letters=0;
int i;
int mywidth,done;
int r=0;
int spacestot=0,spaceswant;

	for (i=0;i<len;i++)
		letters+=F[start+i];
	spaceswant=Width-letters;
	mywidth=Width;
	for (done=0;done<len-1;done++) {
int spacesnow;

		spacesnow=(mywidth-letters)/(len-1-done);
#ifdef DEBUGG
		printf("mywidth=%d,letters=%d,len=%d,done=%d,spacesnow=%d\n",
				mywidth,letters,len,done,spacesnow);
#endif
		if (spacesnow<1)
			return -1;

		r+=(spacesnow-1)*(spacesnow-1);

		letters-=F[start+done];
		mywidth-=F[start+done];
		mywidth-=spacesnow;
		spacestot+=spacesnow;
		}
#if 0
	assert(F[start]<=Width);
#endif
	if (len==1 && F[start]<Width)
		return 500;
#if 0
	assert(!(spacestot!=spaceswant && len==1));
#endif

	return r;
}

int main(void)
{
int i;
char *s,buf[50000],*s2,*s3;
int start,items,badness;

	for (;;) {
		i=scanf("%d\n",&Width);
		assert(i==1);
		if (Width==0)
			break;
		FN=0;
		for (;;) {
			s=fgets(buf,sizeof(buf),stdin);
			assert(s);
			if (*buf=='\n')
				break;
			s=strchr(buf,'\n');
			if (s)
				*s='\0';
			for (s=buf;*s;) {
				while (*s==' ')
					s++;
				if (!*s)
					break;
				s2=strchr(s,' ');
				if (!s2)
					s2=s+strlen(s);
#if 1
				for (s3=s;s3<s2;s3++)
					assert(*s3>=33 && *s3<=126);
#endif
#if 1
				assert(s2-s<=Width);
#endif
				F[FN++]=s2-s;
				s=s2;
				while (*s==' ')
					s++;
				}
			}
		F[FN]=0;
		for (start=FN-1;start>=0;start--) {
			Best[start]=0;
			for (items=1;start+items<=FN;items++) {
				badness=lineeval(start,items);
#ifdef DEBUG
				printf("pass: start=%d,items=%d: badness=%d\n",start,items,badness);
#endif
				if (badness==-1)
					break;
				if (start+items < FN)
					badness+=Best[start+items]-1;
				if (!Best[start] || badness<Best[start])
					Best[start]=badness+1;
				}
			}
		printf("Minimal badness is %d.\n",Best[0]-1);
		}
	return 0;
}