Music

Time limit2sMemory limit128 MB

Summary

Insert non-consecutive rest symbols into three note sequences to equalize their lengths while maximizing a column-matching score, or report impossibility.

Level: Medium7 of 10
Topics: Dynamic programming, String, Combinatorics
Solved: No attempts yet

Problem

Music uses seven notes: C, D, E, F, G, A, and B. You are given three pieces of music. You may insert the rest symbol & at any positions in each piece, and after the insertions all three resulting strings must have the same length.

However, no single piece may contain two or more consecutive & symbols.

Look at the aligned pieces column by column from left to right. The score of one column is defined as follows.

If all three pieces play the same real note, the column scores 3 points.
If exactly two pieces play real notes and those two notes are equal, the column scores 1 point.
Otherwise, the column scores 0 points. In particular, a column with one real note and two & symbols does not score 1 point.

Find the maximum total score obtainable by inserting & symbols into the three pieces. If it is impossible to make the three pieces have the same length while satisfying the rule above, output -1.

Input

Three lines are given, one piece of music per line. Each piece consists only of the seven notes above, and its length is between 1 and 100 inclusive.

Output

Print the maximum total score among all valid alignments on the first line. If no valid alignment exists, print -1.

Examples5

Example 1

Input

GABBCDEACF
GAFGFCBBDEDD
AFAFGCEECDEDF

Expected output

Example 2
Input
```
ABCDEF
BCDEFG
DEFGAB
```
Expected output
```
5
```
Example 3
Input
```
BCDEFGGADEF
BCDE
CDEFGABBA
```
Expected output
```
-1
```

Example 4

Input

GAGABDEDCGAFFAB
DAFFAGAEECCBA
GCBDAAEGEAGAFF

Expected output

Example 5
Input
```
CGCC
C
CC
```
Expected output
```
-1
```