Y-Shaped Necklace Game

On Happy Island, many novel amusement projects let the kids like Xiao Keke have a lot of fun. At this moment, they are playing a game of assembling necklaces as quickly as possible. The necklace is not ordinary – it is a Y-shaped necklace. A large pearl in the center serves as the joint, and from this pearl, three chains of various gems extend.

The rules of the game are as follows: in one operation, you may either remove one gem or attach one gem at one end of any one of the three chains. After a number of operations, the goal is to make all three chains exactly identical. To win the game, you need to achieve this with as few operations as possible.

Note: Each type of gem is available in unlimited supply, and the chains are long enough. Also, even if you remove all the gems (resulting in three chains with no gems), it is considered acceptable as all three chains are identical.

Task: Given the three initial chains represented as strings (each character represents a gem), determine the minimum number of operations required such that all three chains become identical. In one operation you can remove or attach a gem from/to an end of a chain.

Observation: Since you are only allowed to remove gems from the ends, the only contiguous block you can preserve in each chain is a contiguous substring from the original chain. If you can find a non‐empty string S that appears as a contiguous substring in all three chains, you can obtain S in each chain by only removing the gems that are not part of that occurrence, with cost equal to (chain length − |S|). Then, no further operations (i.e. attachments) are required. Otherwise, if no non‐empty common substring is found, you may remove all gems and attach the desired chain. Thus, the optimal strategy is to choose S (which can be empty) to maximize its length, and the total cost is:

Total Operations = (|s1| + |s2| + |s3|) − 3×|S|

where |si| is the length of the i-th chain and |S| is the length of the chosen common substring (note that choosing S as an empty string is allowed).

inputFormat

The input consists of three lines. Each line contains a non-empty string representing a chain. Each character in the string represents a gem.

outputFormat

Output a single integer – the minimum number of operations required to make all three chains identical.

sample

abc
abc
abc

0