This task belonged to the harder ones. At first we make a complete weighted bipartite graph. Its first partition consists of the letters chosen by one player. The second partition consists of words from the wordlist which contain the 2 letters chosen at the beginning of the game. The weight of an edge between a letter c and a word w is |M|+1-|w| (where M is the longest word and |w| denotes the length of the word w) if w contains c and 0 otherwise. Then we find a perfect matching in this graph with maximum weight. A matching in a graph is a set of pairwise disjoint edges. A perfect matching is a matching which contains all vertices of one (the smaller) partition. The weight of a matching is the sum of weights of its edges. We will find a perfect matching with maximum possible weight. It is clear that the words in the maximum matching are different, contain all the characters and the sum of their lengths is minimal because otherwise the matching formed by the words with smaller sum of lengths would have higher weight. If any of the characters is matched with a word with an edge with weight 0 then there exists no solution to the task and we will output -1.

So it is enough to solve the maximum perfect matching problem for weighted complete bipartite
graphs. Let the partitions have sizes N_{1} and N_{2} respectively
(N_{1}<=N_{2}). We will show an O((N_{1}+N_{2})^{4})$
algorithm. Note that there are more efficient algorithms known, but this one was already fast
enough.

The term size of a matching will denote the number of edges in it. The optimal matching of size k (M_{k}) is a
matching whose weight is minimal over all possible matchings of size k. We will find optimal
matchings of sizes 0, 1, ... , N_{1}. M_{0} is clearly an empty set and
M_{N1} is the answer to our problem. We assume that we have found M_{k}
and we find now M_{k+1}.

Let's make some definitions first. Let's have a matching M. Matched edge (vertex) with respect to M
is an edge (vertex) in M. An alternating path is a path whose starts at an unmatched vertex in one
partition and ends at an unmatched vertex in the second partition and the edges along it alternate
between unmatched and matched, that is the first edge along the path is unmatched, the second is
matched, the third is unmatched and so on. Let P_{M} denote the unmatched edges and
Q_{M} the matched edges in M of some path P. The cost of P (cost(P)) is the sum of the
weights of the edges in P_{M} minus the sum of the weights of the edges in Q_{M}.
cost(P)=wt(P_{M})-wt(Q_{M}). By augmenting a matching with an alternating path P we
will denote the "flipping" of the edges in path P - that is every matched edge in P will become
unmatched and vice versa. An augmenting path is an alternating path which will increase the weight
of the matching by augmenting the matching with this path.

Let's go back to the problem of finding M_{k+1} from M_{k}. We find the augmenting
path P with the largest cost. Then we augment M_{k} with P to obtain M_{k+1}. By
definition of cost(P) it follows that wt(M_{k+1})=wt(M_{k})+cost(P). It is easy to
prove that M_{k+1} is indeed the maximum matching of size k+1. So we have to find the
augmenting path with maximum cost. One possible way to do it is to collapse all unmatched vertices
into two new vertices U_{L} and U_{R}. Then we direct all matched edges from left to
right retaining their weights and direct all unmatched edges from right to left and assign them
their negative weight. Than we will find the shortest path between U_{L} and U_{R}
and it is clear that this path will be the augmenting path with the largest cost. The resulting
graph will have no cycles so we can do it by Bellman-Ford algorithm in O(NM) which results to an
algorithm in O(N^{2}M).

The second aproach which is used in the example solution works as follows: We will do it in k
iterations. In the i-th (0<=i<=k) iteration we will find for every vertex w_{r} in one
of the partitions an augmenting path with largest cost to some unmatched vertex in the second
partition considering only paths of length 2i+1 and shorter. Let's call it
c_{i}(w_{r}). The length of any augmenting path can't be longer than 2k+1. The 0-th
iteration is easy. For every vertex w_{r} in one of the partitions we will find its
unmatched neighbour connected with an edge with maximum weight. The i-th iteration works as follows:
We check for every w_{r} whether there exists matched w_{s} in the same partition
such that:
c_{i-1}(w_{s})+wt(w_{r},mate(w_{s}))-wt(w_{s},mate(w_{s}))
> c_{i-1}(w_{r}) (mate(w_{s}) denotes the matched neighbour of vertex
w_{s}), i.e. there is more expensive alternating path to w_{r} that comes directly
from w_{s} via mate(w_{s}) - if so, we update c_{i}(w_{r})
accordingly. Then we will choose such unmatched w_{r} whose augmenting path has largest
cost. Every iteration runs in O(N^{2}), there are at most N iterations for every
M_{k} and 0<=k<=N so our algorithm runs in O(N^{4}).