Scrabble

Bessie is playing Bovine Scrabble, which is just like regular Scrabble except that a player's tray holds T letters (3 ≤ T ≤ 20) instead of always holding 7 letters as in the normal game.

For those who have not played English Scrabble, it is a word game where each player has a set of T letters and uses them to form a word to place on a gameboard, which ends up looking a little like a crossword puzzle. For this task, Bessie plays first and cares only about making a word from one or more of her letters (without worrying about how to fit it onto the board).

Each letter has a value (see the table below). For this task, a word's value is the sum of the values of its letters. Thus the word "TAX" has three letters, each with a value: "T" worth 1 point, "A" worth 1 point, and "X" worth 8 points — total 10 points. No other bonus points are considered in this task. Bessie may use one, some, or all of her letters to make the highest-scoring word.

The game also includes blank letters (represented as "#" in the input). A blank letter can be used to represent any other letter but always receives 0 points, no matter which letter it stands for. Each blank letter may, if desired, represent a different actual letter.

Given T, Bessie's T letters, and a dictionary (a list of words in alphabetical order), determine the most valuable word that can be made from Bessie's letters. If two words have the same value, choose the one that comes first alphabetically. Bessie can always form at least one word from the dictionary with her letters.

Letter values:
      0 points:  # (blank)
      1 point:   A, E, I, L, N, O, R, S, T, U
      2 points:  D, G
      3 points:  B, C, M, P
      4 points:  F, H, V, W, Y
      5 points:  K
      8 points:  J, X
     10 points:  Q, Z

• Line 1: Two integers N and T, where N is the number of words in the dictionary and T is the number of letters in Bessie's tray (3 ≤ T ≤ 20).
• Lines 2..N+1: The dictionary words, one per line, in alphabetical order. Each word consists of uppercase letters A–Z and is at most 20 characters long. The dictionary has fewer than 25,000 words.
• Lines N+2..N+T+1: Each line has a single character from Bessie's tray: an uppercase letter A–Z, or "#" for a blank.

• A single line with the highest-scoring word Bessie can make (with no "#" blanks). If several words tie for the highest value, output the one that comes first alphabetically.