program ikeyb; const Infinity = $3FFFFFFF; var F: array [1..90] of Integer; FreqFrom: array [1..90] of Integer; Cost: array [1..90, 1..90] of Integer; Num: array [1..90, 1..90] of Integer; I: Integer; J: Integer; K: Integer; L: Integer; M: Integer; N: Integer; SetNum: Integer; T: Integer; Keys: string [90]; Letters: string [90]; begin SetNum := 0; Read(T); while T <> 0 do begin Dec(T); Readln(K, L); Readln(Keys); Readln(Letters); for I := 1 to L do Read(F[I]); FreqFrom[L] := F[L]; for I := L - 1 downto 1 do FreqFrom[I] := FreqFrom[I + 1] + F[I]; Cost[K, L] := F[L]; Num[K, L] := 1; for I := L - 1 downto 1 do begin Cost[K, I] := Cost[K, I + 1] + FreqFrom[I]; Num[K, I] := Num[K, I + 1] + 1; end; for I := K - 1 downto 1 do for J := 1 to L do begin Cost[I, J] := Infinity; N := 0; for M := 1 to L - J do begin Inc(N, M * F[J + M - 1]); if N + Cost[I + 1, J + M] <= Cost[I, J] then begin Cost[I, J] := N + Cost[I + 1, J + M]; Num[I, J] := M; end; end; end; Inc(SetNum); Writeln('Keypad #', SetNum, ':'); J := 1; for I := 1 to K do begin Write(Keys[I], ': '); for M := J to J + Num[I, J] - 1 do Write(Letters[M]); Writeln; Inc(J, Num[I, J]); end; Writeln; end; end.