스크래블 | cho.sh

문제

Bessie는 소 버전 스크래블(Bovine Scrabble)을 하고 있습니다. 일반 스크래블과 같지만, 각 플레이어의 글자판(tray)에 항상 7개의 글자가 있는 대신 T개(3 ≤ T ≤ 20)의 글자가 있다는 점만 다릅니다.

영어 스크래블을 해 본 적이 없는 사람을 위해 설명하면, 스크래블은 각 플레이어가 T개의 글자를 가지고 이를 이용해 단어를 만들어 게임판에 놓는 단어 게임으로, 완성된 모습은 크로스워드 퍼즐과 비슷합니다. 이 문제에서 Bessie는 첫 번째 순서이며, 자신의 글자 중 하나 이상을 사용해 단어를 만드는 것에만 관심이 있습니다(게임판에 어떻게 배치할지는 신경 쓰지 않습니다).

각 글자에는 점수가 있습니다(아래 표 참고). 이 문제에서 단어의 점수는 그 단어를 이루는 각 글자의 점수의 합입니다. 예를 들어 단어 "TAX"는 세 글자로 이루어져 있고, 각각 "T" 1점, "A" 1점, "X" 8점이므로 총 10점입니다. 그 밖의 보너스 점수는 이 문제에서 고려하지 않습니다. Bessie는 자신의 글자 중 하나, 일부, 또는 전부를 사용해 점수가 가장 높은 단어를 만들 수 있습니다.

이 게임에는 빈 글자(blank, 입력에서 "#"로 표현)도 포함됩니다. 빈 글자는 어떤 글자든 대신할 수 있지만, 어떤 글자를 선택하더라도 항상 0점을 받습니다. 각 빈 글자는 필요하다면 서로 다른 실제 글자를 대신할 수 있습니다.

T, T개의 글자, 그리고 사전(알파벳 순으로 정렬된 단어 목록)이 주어질 때, Bessie의 글자들로 만들 수 있는 가장 점수가 높은 단어를 구하세요. 두 단어의 점수가 같다면 알파벳 순으로 더 앞서는 단어를 선택합니다. Bessie는 자신의 글자들로 사전에 있는 단어를 항상 하나 이상 만들 수 있습니다.

글자 점수:
      0점:   # (빈 글자)
      1점:   A, E, I, L, N, O, R, S, T, U
      2점:   D, G
      3점:   B, C, M, P
      4점:   F, H, V, W, Y
      5점:   K
      8점:   J, X
     10점:   Q, Z

입력

첫째 줄: 두 정수 N과 T. N은 사전에 있는 단어의 개수, T는 Bessie의 글자판에 있는 글자의 개수입니다 (3 ≤ T ≤ 20).
다음 N개의 줄: 사전의 단어가 알파벳 순으로 한 줄에 하나씩 주어집니다. 각 단어는 대문자 A–Z로만 이루어지며 길이는 20자 이하입니다. 사전에는 25,000개 미만의 단어가 있습니다.
다음 T개의 줄: Bessie의 글자판에 있는 글자가 한 줄에 하나씩 주어집니다. 각 글자는 대문자 A–Z 또는 빈 글자를 나타내는 "#"입니다.

출력

Bessie가 만들 수 있는 가장 점수가 높은 단어를 한 줄에 출력합니다(빈 글자 "#"는 출력하지 않습니다). 점수가 같은 단어가 여러 개라면 알파벳 순으로 가장 앞서는 것을 출력합니다.