Letter Game

Interview

Time limit1sMemory limit512 MB

Summary

Given up to 7 collected letters and a dictionary, find all words or pairs of words with the maximum total letter-value score, using each collected letter at most as often as it appears.

Level: Medium6 of 10
Topics: String, Hash map, Backtracking, Sorting
Solved: No attempts yet

Problem

Figure 1: Each of the 26 lowercase letters and its value.

Letter games are popular both at home and on television. In one version of the game, every letter has a value, and you collect letters to form one or more words that give the highest possible score.

Each letter's value is shown in Figure 1 and in the table below.

letter	a	b	c	d	e	f	g	h	i	j	k	l	m
value	2	5	4	4	1	6	5	5	1	7	6	3	5

letter	n	o	p	q	r	s	t	u	v	w	x	y	z
value	2	3	5	7	2	1	2	4	6	6	7	5	7

Given the letter values, a dictionary of words, and the letters you have collected, find every highest-scoring word or pair of words that can be formed from the collected letters.

No letter may be used more often — in a single word, or in the two words on one line combined — than it appears among the collected letters. A word's score is the sum of the values of its letters, and a pair's score is the sum of the two words' scores.

Input

The first line contains the collected letters as a lowercase string. This string has at least 3 and at most 7 letters, in arbitrary order.

Starting from the second line, a dictionary is given. It consists of at most 40,000 lines, and each line holds one lowercase string of at least 3 and at most 7 letters. The dictionary is sorted alphabetically and contains no duplicates. The dictionary ends with a line containing a single period (.).

Output

On the first line, print the highest achievable score.

On the following lines, print every word and every pair of words whose score equals that highest score, one per line. Write the two words of a pair in non-decreasing alphabetical order, separated by a single space. Do not print the same pair twice; for example, rag prom and prom rag are the same pair, so only one of them is written. A pair may consist of two identical words, in which case that word's letters are used twice.

Sort all printed lines (single words and pairs) in ascending lexicographical order, comparing each line as a whole string, where the separating space (ASCII 32) comes before every letter. If no word or pair can be formed, print only 0.

Examples3

Example 1

Input

prmgroa
profile
program
prom
rag
ram
rom
.

Expected output

24
program
prom rag

Example 2
Input
```
cat
act
cat
.
```
Expected output
```
8
act
cat
```

Example 3

Input

aggrar
gag
gar
rag
.

Expected output

18
gar gar
gar rag
rag rag