CF25E - Test

Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions?

Input

There are several test cases. For each test case there are exactly 3 lines. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105.

Output

For each test case output one number — what is minimal length of the string, containing s1, s2 and s3 as substrings.

Example

Input:
ab
bc
cd
abacaba
abaaba
x

Output:
4
11

Added by:David Gómez
Date:2010-08-17
Time limit:1.089s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:Codeforces - Unofficial Test Cases

hide comments
2019-10-13 01:03:10
@Iqram Mahmud, I am in the same situation, but I don't know how to fix it, can you help me: <snip>
My code get AC on CF.

Last edit: 2022-08-31 22:46:37
2012-11-14 02:28:21 Ravi Kiran
SPOJ: DNALAB is similar!
2010-08-17 09:11:38 Iqram Mahmud
After get Wrong Answer here, I submitted the same code in Codeforces just to check, and it got AC there. I think there is something wrong with your dataset.

RE (David): AC in Codeforces doesn't mean AC here. Check your main, you have some bugs there

RE (smilitude): My bad! I didn't expect a stronger dataset here. Sorry for the complaining.

Last edit: 2010-08-19 00:56:20
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.