Description

The many novel attractions on Happy Island make Xiao Keke and friends very happy. They are now competing in a necklace-threading game; whoever finishes the fastest wins a generous prize.

This is not an ordinary necklace, but a Y-shaped necklace. At the very center there is a big pearl serving as the junction, and from it extend 3 chains strung with various gemstones.

The rules are as follows: each time, you may either take one gemstone off from the end of one of the three chains, or attach one gemstone to the end of one of the three chains. This counts as one operation. After a number of operations, the goal is to make the three chains exactly the same. To win, you must use as few operations as possible.

Assume there are infinitely many of each type of gemstone available, and the chains are long enough. Can you help Xiao Keke win?

Note: Because there is no special requirement on the number of gemstones on the Y-shaped necklace, removing all gemstones is also an acceptable plan (three strings without gemstones are identical).

Input Format

There are $3$ lines, describing the three chains of the Y-shaped necklace. Each line begins with an integer $N$, indicating the number of gemstones initially on this chain, followed by a space, and then $N$ uppercase letters representing the gemstones on this chain. Each letter denotes a type of gemstone. The leftmost character of the string is the gemstone closest to the big pearl, and the rightmost character is the gemstone at the end of the chain.

Output Format

Output a single integer: the minimum number of operations required.

3 CAT
3 TAC
5 CATCH

8

Hint

For $50\%$ of the testdata, $N\leq 20$.

For $100\%$ of the testdata, $1\le N\le 50$.

Translated by ChatGPT 5