ZOJ Problem Set - 3615
After the celebration, all the members of the school choir decided to have a party to enjoy a good time. In the school choir there are n boys and m girls. In order to have a happy dancing time, Cici wants to divide boys and girls into pairs (a pair is a boy and a girl). So, she asks every boy and every girl about their evaluation about others.
After Cici asking everyone about their evaluation, she finds that she can get a GI(good impression) number by one's sentence. Here, we define the GI from A's sentence about B is X * Y, X is the position of B's name first appeared in the sentence (Indexed from 1), Y is the times that B's name appeared.
Explain about monkey language:
"ababa": For name "aba", it appears twice on the position 1 and position 3.
"I love Kity": For name "Kity", it appears once on the position 8. For name "Kit", it appears once on the position 8. For "ity", it appears once on the position 9.
So, Cici wants to know the maximal sum of GI she can get by an optimalizing divided way.
The input file consists of several test cases. The first line of each test case contains two integers m, n (0 < m + n < 200), indicating m boys and n girls.
Then following m + n lines with m lines for m boys and n lines for n girls. Each line consists a sentence in the format "A: B, C ... D...", which A, B, C D are others' name and "..." is other words. All the m + n names are distinct, each name is no longer than 20 characters and the sentence is no longer than 10000 characters.
For each test case, print a number of the maximal sum GI Cici can get.
3 2 Kit: I love KityKityMityMity Sam: Kity is a QmOnkey Bob: I don't like anyone. Kity: Sam is a so smart. Mity: Sam is good.
Author: LI, Fei
Contest: ZOJ Monthly, June 2012