{ Dežimtoji moksleivi— informatikos olimpiada }
{ Tre‡iojo etapo antroji dalis, Vyresni—j— grup‚ }
{ U‘davinys "’od‘i— ratas" }
{$M 65520,0,655360}
program zodziu_ratas;
  const MAX = 100; { maksimalus ‘od‘i— skai‡ius }
        ILGIS = 20; { maksimalus ‘od‘io ilgis }
        PRAD = 'RATAS.DAT';
        REZ = 'RATAS.REZ';
  type zodziai = array [1..MAX] of
             record
               zod: string[ILGIS]; { pats ‘odis }
               poz_r, { jo pozicija rate }
               poz_s: integer; { ir konstruojamame sprendinyje }
               dalis: boolean; { ar Ťtrauktas Ť rat… kaip kito ‘od‘io dalis }
             end;
       kv_lent = array [1..MAX, 1..MAX] of set of 0..ILGIS;

  { ‘emiau apražyti globalieji kintamieji }
  var n,           { pozicij— skai‡ius rate }
      zod_sk: integer; { duot— ‘od‘i— skai‡ius }
      z: zodziai;  { duotieji ‘od‘iai }


  procedure vienas_zodis (var maks: integer);
  { ižnagrin‚ja atskir… atvejŤ, kai rat… sudaro vienas nepersiklojantis }
  { ‘odis. ’inoma, kad iki žiol nei vieno sprendinio nerasta }
    var i: integer;
  begin
    i := 0; maks := 0;
    repeat
      i := i + 1;
      if length(z[i].zod) = n
         then begin
                z[i].poz_r := 1;
                maks := n;
              end;
    until (maks <> 0) or (i > n)
  end; { vienas_‘odis }

  procedure galunes (var g: kv_lent);
    { u‘pildo masyv… g. Jei s priklauso g[i, j], tai reižkia, kad }
    { s paskutini—j— i-tojo ‘od‘io raid‘i— sutampa su s pirm— j-ojo }
    { ‘od‘io raid‘i— }
      var i, j, k, viso: integer;
          pir, ant: string;
    begin
      for i := 1 to zod_sk do
        for j := 1 to zod_sk do
          begin
            g[i, j] := [];
            k := 1; { prad‘ioje imsime tokio ilgio gal–nŠ }
            while (k <= length(z[i].zod)) and (k <= length(z[j].zod)) do
              { ar sutaps ilgio k galas su prad‘ia }
              begin
                { atskirsime k ilgio gal–nŠ bei prad‘i… }
                pir := copy (z[i].zod, length(z[i].zod)-k+1, k);
                ant := copy (z[j].zod, 1, k);
                if pir = ant
                   then g[i, j] := g[i, j] + [k];
                k := k + 1;
              end;
          end;
  end; { gal–n‚s }

  procedure dalys (var suma: integer);
  { Ť u‘baigt… rat… Ťtrauki… ‘od‘ius, kurie yra kit— ‘od‘i— dalys }
    var i, j: integer;
  begin
    for i := 1 to zod_sk do
      if z[i].poz_s > 0
      then for j := 1 to zod_sk do
             if (z[j].poz_s = 0) and (pos(z[j].zod, z[i].zod) > 0) and
                (i <> j)
             { j-as ‘odis n‚ra rate ir yra i-tojo ‘od‘io dalis }
             then begin
                    z[j].poz_s := z[i].poz_s + pos(z[j].zod, z[i].zod) - 1;
                    suma := suma + length(z[j].zod);
                    z[j].dalis := true
                  end;
  end; { dalys }

  procedure delioti (var galima: boolean; { ar galima sudaryti rat… }
                     var viso,   { kiek ‘od‘i— jame tilps }
                     maks: integer { ‘od. ilgi— suma geriausiame sprendinyje });
  { proced–ra, gaubianti rekursinŠ proced–r… }
     { ‘emiau apražyti kintamieji global–s rekursinei proced–rai }
    var g: kv_lent;    { g[i, j] rodo kelios i-tojo ‘od‘io pabaigos }
                        { raid‚s sutampa su j-tojo ‘od‘io prad‘ia }
        pirm: integer;  { ‘od‘io, kuriuo pradedamas ratas, numeris }
    {----------------------------------------------------------------}
    procedure deti (i, { Ťražomo ‘od‘io indeksas }
                    r,   { raid‘i—, sutampan‡iu su ankstesniu ‘od‘iu, sk. }
                    uzim, { u‘imt— pozicij— skai‡ius }
                    suma: integer { ‘od‘i— ilgi— suma });
    { rekursin‚ proced–ra "d‚ti" Ť rat… Ťražo i-t…jŤ ‘odŤ }
      var ilgumas, k, j: integer;
    begin
      { Ťražome i-t…jŤ ‘odŤ; sutama pirmosios r raid‚s }
      ilgumas := length(z[i].zod); { i-tojo ‘od‘io ilgis }
      suma := suma + ilgumas;
      z[i].poz_s := uzim - r + 1;
      uzim := uzim + ilgumas - r;
      { jei d‚liojimas baigtas }
      if uzim > n
      then begin
             if (uzim-n) in g[i, pirm] { jei ratas u‘sidaro }
             then begin
                    { prijungiame ‘od‘ius, kurie yra kit— ‘od‘i— dalys }
                    dalys (suma);
                    { ar radome geresnŤ sprendinŤ }
                    if suma > maks
                       then begin
                              maks := suma;
                              for k := 1 to zod_sk do
                                z[k].poz_r := z[k].poz_s;
                            end;
                    { gr…‘iname reikžmes - iž rato pažaliname ‘od‘ius, }
                    { kurie yra kit— ‘od‘i— dalys }
                    for k := 1 to zod_sk do
                      if z[k].dalis
                         then begin
                               z[k].dalis := false;
                               z[k].poz_s := 0;
                              end;
                  end { jei ratas u‘sidaro }
           end { jei d‚liojimas baigtas }
      else { d‚liojame toliau }
        for j := pirm+1 to zod_sk do { pirmuosius ‘od‘ius praleid‘iame }
            if (z[j].poz_s = 0) and (g[i, j] <> [])
               { jei j-as ‘odis n‚ra rate ir jŤ galima jungti prie i-tojo }
               then for k := 1 to length(z[j].zod) do
                      if k in g[i, j]
                         then deti (j, k, uzim, suma);
      { atstatome reikžmes }
      z[i].poz_s := 0;
      z[i].dalis := false;
    end; { d‚ti }
    {----------------------------------------------------------------}

    var i, uzim, suma: integer;
  begin
    galunes (g);
    for i := 1 to zod_sk do
      with z[i] do
        begin
         poz_r := 0; { ‘odis neŤtrauktas Ť rat… }
         poz_s := 0; { nei Ť konstruojam… sprendinŤ }
         dalis := false;
        end;
    maks := 0; { maksimalus sutalpint— raid‘i— skai‡ius optimaliame }
               { sprendinyje }
    uzim := 0;  { neu‘imta nei viena rato pozicija }
    suma := 0;
    { patikrinsime, ar rat… gali sudaryti vienas nepersiklojantis ‘odis }
    if n <= ILGIS
       then vienas_zodis (maks);
    { iežkosime kit— sprendini— }
    for pirm := 1 to zod_sk do  { rat… prad‚sime i-tuoju ‘od‘iu }
      deti (pirm, 0, uzim, suma);
        { i-tasis ‘odis bus ražomas nuo 1-osios pozicijos, n‚ra raid‘i—, }
        { sutapusi— su priež tai buvusiu ‘od‘iu }
    { baigŠ d‚lioti ‘od‘ius rasime kiek ‘od‘i— tilpo Ť rat… }
    viso := 0;
    for i := 1 to zod_sk do
      if z[i].poz_r <> 0
         then viso := viso + 1;
    galima := viso <> 0;
  end; { d‚lioti }

  var f: text;
      i, viso, maks: integer;
      galima: boolean;
begin
  assign (f, PRAD);
  reset (f);
  readln (f, n, zod_sk);
  for i := 1 to zod_sk do
    readln (f, z[i].zod);
  close (f);
  delioti (galima, viso, maks);
  assign (f, REZ);
  rewrite (f);
  if not galima
     then writeln (f, 'NEGALIMA')
     else begin
            writeln (f, maks, ' ', viso);
            for i := 1 to zod_sk do
              if z[i].poz_r <> 0
                 then begin
                        writeln (f, z[i].poz_r);
                        writeln (f, z[i].zod);
                      end;
          end;
  close (f);
end.