#include <stdio.h>
#include <string.h>

#define MAX_LINE 103
#define MAX_ROWS 10010

int linelen;
int rows;

struct radek {
  int delky[MAX_LINE];
  int slov;
  int znaku;
  int badness;

  radek();  
  int add_word_end(int delka);  // ret 0/1
  int add_word_beg(int delka);  // ret 0/1
  int delka_end();
  int delka_beg();
  int del_word_end();  // 
  int del_word_beg();  // 
  int comp_badness();
  int comp_badness(int delka, int plus); // 0-minus delka, 1-plus delka
  void del_all();
};

radek::radek() {
  slov = znaku = badness = 0;
}

int radek::delka_end() {
  return delky[slov-1];
}

int radek::delka_beg() {
  return delky[0];
}

void radek::del_all(){
  slov = znaku = badness = 0;
}

int radek::comp_badness(int delka, int plus) {
  int bad = badness, newb;
  if (plus == 1)
  {    
    int tmpzn = znaku + delka;
    int tmpsl = slov+1;
    if (tmpzn + slov > linelen) return 0x7FFF;
    else {
      znaku = tmpzn;
      slov = tmpsl;
      newb = comp_badness();
      znaku -= delka;
      slov--;
    }
  } else {
    int tmpzn = znaku - delka;
    int tmpsl = slov-1;
    if (tmpsl < 1) return 0x7FFF;
    else {
      znaku = tmpzn;
      slov = tmpsl;
      newb = comp_badness();
      znaku += delka;
      slov++;
    }
  }
  badness = bad;
  return newb;
}

int radek::del_word_end() {
  if ( slov <= 1 ) return 0;
  znaku -= delky[--slov];
  delky[slov] = 0;
  return 1;
}

int radek::del_word_beg() {
  if (slov <= 1 ) return 0;
  znaku -= delky[0];
  for (int i=1; i<slov; i++)
    delky[i-1] = delky[i];
  slov--;
  return 1;
}

int radek::add_word_beg(int delka) {
  int tmpzn = znaku+delka;
  if (tmpzn + slov > linelen)
    return 0;
  for (int i=slov-1; i>=0; i--)
    delky[i+1] = delky[i];
  delky[0] = delka;
  znaku = tmpzn;
  slov++;
  return 1;
}

int radek::add_word_end(int delka) {
  int tmpzn = znaku+delka;
//  printf("%d %d %d\n", znaku, slov, linelen);
  if (tmpzn + slov > linelen)
    return 0;
  delky[slov++] = delka;
  znaku = tmpzn;
  return 1;
}

int radek::comp_badness() {
  int prazd = linelen-znaku;
  if (slov == 1 && prazd > 0)
    badness = 500;
  else
  {
    int mezer = slov-1;
    int d1 = prazd/mezer;
  int n1 = prazd % (d1*mezer);
  int d0 = d1-1;
  int n0 = mezer-n1;
  
      badness = d1*d1*n1+d0*d0*n0;
  }
  
  printf("badness: %d\n", badness);
  return badness;
}

radek* row[MAX_ROWS];

int main()
{
  char str[110];
  char *sl;
  int changed=1;
  int jekonec = 0;
  
  for (int i=0; i<MAX_ROWS; i++)
    row[i] = new radek;
  while(1) {
    rows = 0;
    scanf("%d\n", &linelen);
    while(1) {
      char *err;
      char *sep = str;
      err = gets(str);
      if (err == 0 || str[0] == 0) break;
      jekonec = 0;
      while((sl=strsep(&sep," ")) != NULL)
      {
        radek *thisrow = row[rows];
	int len = strlen(sl);
	if (len>0)
	{
	  int x;
	  for( x=0; x<strlen(sl); x++)
	    if (sl[x] == ' ') break;
	  thisrow->add_word_end(x);
	}
//	printf("%s\n", sl);
      }
//      printf("%d\n", str[0]);
      rows++;
    }
//    printf("ahoj\n");
    if (rows <= 0) { 
      if(jekonec) break;
      jekonec=1; 
      continue; 
    }
    for (int indi=0; indi<rows; indi++)
      row[indi]->comp_badness();
    changed=1;
    while(changed)
    {
      changed=0;
      int ind;
      for (ind=1; ind<rows; ind++)
      {
        int bad1 = row[ind-1]->badness;
        int bad2 = row[ind]->badness;
        int movedlen = row[ind-1]->delka_end();
        int newb1 = row[ind-1]->comp_badness(movedlen,0);
        int newb2 = row[ind]->comp_badness(movedlen,1);
        if (bad1+bad2 < newb1+newb2)
        {
          changed = 1;
          row[ind-1]->del_word_end();
	  row[ind]->add_word_beg(movedlen);
	  row[ind]->badness = bad2;
	  row[ind-1]->badness = bad1;
	  ind--;
	  printf("dolu %d %d\n", bad1, bad2);
	  continue;
        }
      }
            printf("dalsi1\n");

      for (ind=rows-1; ind>0; ind--)
      {
        int bad1 = row[ind-1]->badness;
	int bad2 = row[ind]->badness;

	int movedlen = row[ind]->delka_beg();
            printf("dalsi1%d\n", movedlen);

	int newb1 = row[ind-1]->comp_badness(movedlen,1);
            printf("dalsi1\n");

	int newb2 = row[ind]->comp_badness(movedlen,0);
	            printf("dalsi1\n");

	if (bad1+bad2 < newb1+newb2)
	{
	  changed=1;
	  row[ind]->del_word_beg();
	  row[ind-1]->add_word_end(movedlen);
	  row[ind]->badness = bad2;
	  row[ind-1]->badness = bad1;
	  ind++;
	  printf("nahoru %d %d\n", bad1 , bad2);
	  continue;
	}
      }
            printf("dalsi1\n");

    }
    int total=0;
    int ind;
    for ( ind=0; ind<rows; ind++ )
      total += row[ind]->badness;
    printf("Minimal badness is %d.\n", total);
    for ( ind=0; ind<rows; ind++ )
      row[ind]->del_all();
  }
  return 0;
}