P2753 [USACO4.3] Letter Game

Given $3 \sim 7$ cards and at most $4 \times 10^4$ valid words, use the cards to form one or more valid words (i.e., a "phrase"), where each card can be used at most once, so that the sum of the values of the cards used is maximized, and output all optimal solutions. The value of a card depends on the letter on it; the correspondence is as follows: ```plain [Letter] a b c d e f g h i j k l m n o p q r s t u v w x y z [Value] 2 5 4 4 1 6 5 5 1 7 6 3 5 2 3 5 7 2 1 2 4 6 6 7 5 7 ``` 

The first line contains $3 \sim 7$ lowercase letters, indicating the letters on your cards. The next up to $4 \times 10^4 + 1$ lines each contain $3 \sim 7$ lowercase letters representing a valid word, with `.` as the end-of-input marker. All valid words are guaranteed to be distinct and given in ascending lexicographic order.

On the first line, output an integer representing the maximum score. Then output several lines (sorted in ascending lexicographic order). Each line contains one or more words (also sorted in ascending lexicographic order), representing the word or "phrase" formed in each optimal solution. Two phrases that differ only in the order of words should be considered the same phrase. In that case, you should output the words within that phrase in ascending lexicographic order.

The problem statement translation is from NOCOW. USACO Training Section 4.3. Translated by ChatGPT 5