program ikey;
const
  maxn=100;
  maxf=100000;
var
  t:integer;
  case_no:integer;
  k,l:integer;
  inf:integer;
  cost:array[0..maxn,0..maxn] of integer;
  f:array[1..maxn] of integer;
  key,letter:string;
  a:array[0..maxn,0..maxn] of integer;
  
  procedure read_data;
  var
    i:integer;
  begin
    readln(k,l);
    readln(key);
    readln(letter);
    for i:=1 to l do readln(f[i]);
  end;
  
  procedure init;
  var
    i:integer;    
  begin
    inf:=1;
    for i:=1 to 90 do inf:=inf+i*maxf;
{    Writeln('inf=',inf);}
  end;
  
  procedure write_answer(letters,keys:integer);
  var
    i,j:integer;
  begin
    if (letters=0) and (keys=0) then Writeln('Keypad #',case_no,':')
    else begin
      j:=0;
      for i:=0 to letters-1 do 
        if (A[letters,keys]=A[i,keys-1]+Cost[i+1,letters]) then begin
	  j:=i;
	  break;
        end;
      Write_answer(j,keys-1);
      Write(key[keys],': ');
      for i:=j+1 to letters do Write(letter[i]);
      Writeln;
    end;        
  end;
  
  procedure solve;
  var
    i,j:integer;
    c:integer;
    keys,letters:integer;
  begin
    for i:=1 to l do cost[i,i]:=f[i];
    for i:=1 to l do 
      for j:=i+1 to l do cost[i,j]:=cost[i,j-1]+(1+j-i)*F[j];
    
    for i:=0 to l do
      for j:=0 to k do a[i,j]:=inf;
    for i:=0 to k do a[0,i]:=0;
    
    
    for keys:=1 to k do 
      for letters:=keys to l do begin
        a[letters,keys]:=A[keys-1,keys-1]+Cost[keys,letters];
        for j:=keys to letters do 
	begin
	  c:=Cost[j,letters]+A[j-1,keys-1];
{	  if (keys<2) then
	  Write('c=',c,' ');}
	  if (c<A[letters,keys]) then A[letters,keys]:=c;
{	  else break;}
	end;
{	Write(a[letters,keys],' ');
	if (letters=l) then Writeln;}	
      end;  
    Write_answer(letters,keys);       
  end;
  
begin
  case_no:=0;
  init;
  readln(t);
  while (t>0) do begin
    inc(case_no);
    dec(t);
    read_data;
    solve;
    Writeln;    
  end;
end.