{  ACM International Collegiate Programming Contest
   Central European Regional Contest 2000
   
   Problem I - I-Keyboard
   Martin Kacer
}

Program SMS;
Const MAX_CHARS	= 128;
	MAX_KEYS	= 128;
Var TaskCnt, TaskNum  : Integer;
	NumChars, NumKeys : Integer;
	KeyNames		  : Array [1..MAX_KEYS] of Char;
	CharNames		  : Array [1..MAX_CHARS] of Char;
	CharScore		  : Array [1..MAX_CHARS] of Integer;
	BestScore		  : Array [1..MAX_KEYS, 1..MAX_CHARS] of Integer;
	BestPrev		  : Array [1..MAX_KEYS, 1..MAX_CHARS] of Integer;
	LastCharOnKey	  : Array [1..MAX_KEYS] of Integer;
	I, J, K			  : Integer;
	TmpOne, TmpCnt	  : Integer;

Begin
	Readln (TaskCnt);
	For TaskNum:= 1 to TaskCnt do
	Begin
		WriteLn ('Keypad #', TaskNum, ':');
		ReadLn (NumKeys, NumChars);
		For J:= 1 to NumKeys do Read (KeyNames[J]);
		ReadLn;
		For I:= 1 to NumChars do Read (CharNames[I]);
		ReadLn;
		For I:= 1 to NumChars do ReadLn (CharScore[I]);
		BestScore[1,1]:= CharScore[1];
		if (NumChars > 1) then For I:= 2 to NumChars do
			BestScore[1,I]:= BestScore[1,I-1] + I * CharScore[I];
		if (NumKeys > 1) then For J:= 2 to NumKeys do
			For I:= J to NumChars do
			Begin
				TmpOne:= CharScore[I];
				TmpCnt:= TmpOne;
				BestScore[J,I]:= TmpOne + BestScore[J-1,I-1] + 1;
				For K:= I-1 downto J-1 do Begin
					if (TmpOne + BestScore[J-1,K] <= BestScore[J,I]) then
					Begin
						BestScore[J,I]:= TmpOne + BestScore[J-1,K];
						BestPrev[J,I]:= K;
					End;
					TmpOne:= TmpOne + TmpCnt + CharScore[K];
					TmpCnt:= TmpCnt + CharScore[K];
				End;
			End;

		K:= NumChars;
		For J:= NumKeys downto 1 do Begin
			LastCharOnKey[J]:= K;
			K:= BestPrev[J,K];
		End;
		K:= 1;
		For J:= 1 to NumKeys do Begin
			Write (KeyNames[J], ': ');
			For I:= K to LastCharOnKey[J] do Write (CharNames[I]);
			WriteLn;
			K:= LastCharOnKey[J] + 1;
		End;
		WriteLn;
	End;
End.
