Letter Game Maximum Score

A popular TV game involves forming words with collected letters, where each letter has a specific point value. You are given a list of English words and a collection of letters. Your task is to choose either a single word or a pair of words (separated by a space) such that the total score is maximized. The score of a word is defined as

$$score(word)=\sum_{c\in word} value(c)$$

with the letter values given as follows:

\[ \begin{aligned} A, E, I, L, N, O, R, S, T, U &= 1,\\ D, G &= 2,\\ B, C, M, P &= 3,\\ F, H, V, W, Y &= 4,\\ K &= 5,\\ J, X &= 8,\\ Q, Z &= 10. \end{aligned} \]

When forming a pair of words, the combined letters of both words must be a subset of the collected letters (each letter can be used at most as many times as it appears in the collection). If no word or word pair can be formed, output an empty line.

inputFormat

The first line contains an integer $$N$$ representing the number of words in the dictionary. Each of the following $$N$$ lines contains one word (composed of uppercase letters only). The last line contains a string of uppercase letters representing the collected letters.

outputFormat

Output a single line containing either one valid word or a pair of valid words (separated by a single space) that yields the maximum total score. If multiple answers achieve the same maximum score, output any one of them. If no valid word or word pair can be formed, output an empty line.

sample

6
APPLE
PLEA
PEAL
LAP
PALE
ALE
AELPP

APPLE