#include <stdio.h>

int n,width;
int wl[10000];

int optA[10000];
int optB[10000];
int *opt1, *opt2;

void set (int p,int val) {
  if (opt2[p] < 0 || opt2[p] > val) {
    opt2[p] = val;
  }
}

int getcost (int delta, int spc) {
  int each = delta / spc;
  int extra = delta % spc;
  int c = (spc - extra)*each*each + extra * (each+1)*(each+1);
  return c;
}


int main()
{
  char l[200];
  int i,j;

  while(1)
  {
    n=0;
    gets(l);
    sscanf(l,"%d",&width);
    if (width==0)
      break;
    while (1)
    {
      gets(l);
      for (i=0;l[i] && (l[i] < 33 || l[i] > 126);i++);
      if (!l[i])
        break;
      while (l[i])
      {
        for (j=i;l[j] >=33 && l[j] <=126;j++);
        wl[n++] = j-i;
        for (i=j;l[i] && (l[i] < 33 || l[i] > 126);i++);
      }

    }

    opt1 = optA;
    opt2 = optB;

    for (i = 0; i <= n;i++)
      opt1[i] = -1;

    opt1[0] = 0;

    while (1) {
      
      for (i = 0; i <= n;i++)
        opt2[i] = -1;

      for (i = 0; i < n; i++) {

        int cost = opt1[i];
        int l = wl[i];

        if (cost < 0)
          continue;

        if (l == width)
          set(i+1, cost);
        else {
          int p = 1;
          int spc = 0;
          set (i+1, 500 + cost);
          for (p++ ; p+i <= n; p++) {
            l += wl[p+i-1] + 1;
            spc++;
            if (l > width)
              break;
            set(i+p, cost + getcost(width-l,spc));
          }
        }
       
      }



      /* ok, co kdyz uz to je? */
      if (opt2[n] >= 0) {
        printf("Minimal badness is %d.\n",opt2[n]);
        break;
      }

      {
        int *p = opt1;
        opt1 = opt2;
        opt2 = p;
      }
    }
  }
  return 0;
}