Stari mornar Đura je odavno zapao u demenciju, pa se često gubi u parkovima, gradskom prevozu i šahovskim turnirima. Njegov unuk je odlučio da mu za 90. rođendan kupi mobilni telefon kako bi u svakom trenutku mogao da obavesti rodbinu o svom kretanju. Pošto je Đura u ratu izgubio sluh, on može da komunicira isključivo sms porukama. Đurine stare kosti je u poslednje vreme zahvatila i reuma tako da kucanje poruka za njega predstavlja izuzetan napor. Kako je njegov mobilni jako skup i kvalitetan, moguće je menjati raspored slova na tasterima, pod uslovom da na svakom tasteru ostane isti broj slova (na svim po 3 slova, osim "1" na kome nema slova, "0" na kome je samo razmak, i "7" i "9" na kome se nalaze po 4 slova). Vaš zadatak je da za zadati tekst sms poruke rasporedite slova engleskog alfabeta po tasterima od "2" do "9" tako da Đura otkuca poruku sa što manjim brojem pritisaka.

Napomena:

Ako se na tasteru nalaze, redom, slova "a", "b" i "c", da bi se otkucalo "a" potreban je jedan pritisak, "b" dva, a "c" tri pritiska.

Ulaz:

U prvom redu ulazne datoteke ZAD4.DAT nalazi se broj N (N ≤ 20000), broj reči u tekstu. U svakom od narednih N redova se nalazi po jedna reč, dužine manje od 20 slova. Reči se sastoje isključivo od malih slova engleskog alfabeta, i smatra se da se između dve reči nalazi blanko karakter.

Izlaz:

U prvom redu izlazne datoteke ZAD4.RES treba ispisati broj pritisaka koji je potreban da bi se otkucala poruka (računajući i pritiske na "0", odnosno blanko karakter). Od drugog do devetog reda izlazne datoteke potrebno je ispisati dobijeni raspored i to, u drugom redu slova koja su raspoređena na taster "2", u trećem raspored za taster "3" itd.

Primer:

7
krenuo
sam
na
kalemegdan 
da
hranim
golubove

54
alc
erf
nuj
mbp
ohq
dity
gsw
kvxz

Slova koja se češće javljaju u tekstu treba staviti na čelna mesta tastera kako bi se kucala sa sto manje pritisaka. Potrebno je prebrojati broj pojavljivanja svakog slova u tekstu, sortirati slova u nerastući niz i prvih osam slova proizvoljno rasporediti na osam tastera, na svaki po jedno slovo. Zatim je potrebno sledećih šesnaest slova rasporediti na isti način, po osam, i konačno dva preostala slova dodeliti tasterima "7" i "9".

#include <iostream.h>
#include <fstream.h>

long int a[26], b[26], n, tot = 0;
char tast[8][4];
int clicks[26];


void init()
{
  for (int i = 0; i <= 25; i++) 
  {
    a[i] = 0;
    clicks[i] = 0;
  }

  for (i = 0; i <= 7; i++)
  {
    for (int j = 0; j <= 3; j++) tast[i][j] = 0;
  }

}
void save()
{
  ofstream gout("zad4.res");

  gout << tot << endl;

  for (int i = 0; i <= 7; i++)
  {
    for (int j = 0; j <= 3; j++)
      if (tast[i][j] != 0) gout << tast[i][j];

    gout << endl;
  }
}
void load()
{
  ifstream gin("zad4.dat");
  char inBuf[25];

  gin >> n;
  gin.getline(inBuf, 25);

  for (long int i = 1; i <= n; i++)
  {
    gin.getline(inBuf, 25);

    for (long int j = 0; inBuf[j] != 0; j++) a[inBuf[j] - 97]++;
  }
}

void solve()
{
  long int m;
  int spot, i, j, k;

  for (i = 0; i <= 25; i++) b[i] = a[i];

  for (i = 0; i <= 2; i++)
  {
    for (j = 0; j <= 7; j++)
    {
      m = -1;
      spot = 0;
      for (k = 0; k <= 25; k++)
      {
        if (a[k] > m)
        {
          m = a[k];
          spot = k;
        }
      }

      tast[j][i] = spot + 97;
      a[spot] = -1;
      clicks[spot] = i + 1;
    }
  }

  for (i = 0; a[i] == -1; i++); tast[5][3] = i + 97; clicks[i] = 4; a[i] = -1;
  for (; a[i] == -1; i++); tast[7][3] = i + 97; clicks[i] = 4;

  tot = 0;
  for (i = 0; i <= 25; i++) tot += clicks[i] * b[i];

  tot += n - 1;

}



int main()
{
  load();
//  qsort(0, 25);
  solve();
  save();
  return 0;
}