글자 게임

그림 1: 26개의 소문자 알파벳과 각 글자의 점수.

글자 게임은 가정에서도, 텔레비전에서도 인기가 많습니다. 이 게임의 한 형태에서는 모든 글자에 점수가 매겨져 있고, 모은 글자들로 하나 이상의 단어를 만들어 가능한 한 높은 점수를 얻는 것이 목표입니다.

각 글자의 점수는 그림 1과 아래 표에 나와 있습니다.

글자 점수, 영어 단어 사전, 그리고 모은 글자들이 주어질 때, 이 글자들로 만들 수 있는 가장 높은 점수의 단어 또는 단어 쌍을 모두 찾으세요.

하나의 단어 안에서든, 한 줄에 함께 쓰인 두 단어를 합쳐서든, 어떤 글자도 모은 글자들에 나타나는 횟수보다 더 많이 사용할 수 없습니다. 단어의 점수는 그 단어를 이루는 글자들의 점수 합이고, 단어 쌍의 점수는 두 단어의 점수 합입니다.

첫째 줄에는 모은 글자들이 소문자 문자열로 주어집니다. 이 문자열은 3자 이상 7자 이하이며, 순서는 임의입니다.

둘째 줄부터는 사전이 주어집니다. 사전은 최대 40,000줄로 이루어져 있고, 각 줄에는 3자 이상 7자 이하의 소문자 문자열이 하나씩 들어 있습니다. 사전은 알파벳 순으로 정렬되어 있으며 중복되는 단어가 없습니다. 사전의 끝에는 마침표(.) 하나만 있는 줄이 옵니다.

첫째 줄에 얻을 수 있는 가장 높은 점수를 출력합니다.

그 다음 줄부터는 이 최고 점수와 같은 점수를 갖는 모든 단어와 단어 쌍을 한 줄에 하나씩 출력합니다. 두 단어로 이루어진 쌍은 두 단어를 알파벳 오름차순으로 정렬하여 공백 한 칸으로 구분해 한 줄에 씁니다. 같은 쌍을 두 번 출력하지 않습니다. 예를 들어 rag prom과 prom rag은 같은 쌍이므로 한 번만 씁니다. 하나의 쌍은 같은 단어 두 개로 이루어질 수도 있으며, 이 경우 그 단어의 글자를 두 번 사용합니다.

출력하는 모든 줄(단어와 단어 쌍)은 줄 전체를 문자열로 보고 사전순 오름차순으로 정렬합니다. 이때 두 단어를 구분하는 공백(ASCII 32)은 어떤 알파벳보다도 앞에 옵니다. 만들 수 있는 단어나 쌍이 하나도 없으면 0만 출력합니다.