#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

char A[2020],B[2020],C[2020];
ll An, Bn, Cn;
ll i, j, k;
bool mkab[20202], mkac[20202], mkbc[20202];

void mkcalc(char *sa,char *sb,bool *mk){
    ll i,j;
    for (i = 0; sa[i];++i){
        for (j = 0; sb[j];++j){
            if(sa[i]!='?'&&sb[j]!='?'&&sa[i]!=sb[j]){
                mk[i - j + 10101] = true;
            }
        }
    }
}

int main(){
    scanf("%s%s%s", A, B, C);
    An = strlen(A);
    Bn = strlen(B);
    Cn = strlen(C);
    mkcalc(A, B, mkab);
    mkcalc(A, C, mkac);
    mkcalc(B, C, mkbc);

    ll ans = 101010;
    fornum(i,-4040,4040){
        fornum(j,-4040,4040){
            if(!mkab[i+10101]&&!mkac[j+10101]&&!mkbc[j-i+10101]){
                ans = min(ans, max(An, max(i + Bn, j + Cn)) - min(0ll, min(i, j)));
            }
        }
    }
    printf("%lld", ans);

    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

Snuke has a string s. From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

* Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with `?`s.



For example, if s is `mississippi`, we can choose the substring `ssissip` and replace its 1-st and 3-rd characters with `?` to obtain `?s?ssip`.

You are given the strings a, b, and c. Find the minimum possible length of s.

Constraints

* 1 \leq |a|, |b|, |c| \leq 2000
* a, b, and c consists of lowercase English letters and `?`s.

Input

Input is given from Standard Input in the following format:


a
b
c


Output

Print the minimum possible length of s.

Examples

Input

a?c
der
cod


Output

7


Input

atcoder
atcoder
???????


Output

7

### Response

```cpp
#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

char A[2020],B[2020],C[2020];
ll An, Bn, Cn;
ll i, j, k;
bool mkab[20202], mkac[20202], mkbc[20202];

void mkcalc(char *sa,char *sb,bool *mk){
    ll i,j;
    for (i = 0; sa[i];++i){
        for (j = 0; sb[j];++j){
            if(sa[i]!='?'&&sb[j]!='?'&&sa[i]!=sb[j]){
                mk[i - j + 10101] = true;
            }
        }
    }
}

int main(){
    scanf("%s%s%s", A, B, C);
    An = strlen(A);
    Bn = strlen(B);
    Cn = strlen(C);
    mkcalc(A, B, mkab);
    mkcalc(A, C, mkac);
    mkcalc(B, C, mkbc);

    ll ans = 101010;
    fornum(i,-4040,4040){
        fornum(j,-4040,4040){
            if(!mkab[i+10101]&&!mkac[j+10101]&&!mkbc[j-i+10101]){
                ans = min(ans, max(An, max(i + Bn, j + Cn)) - min(0ll, min(i, j)));
            }
        }
    }
    printf("%lld", ans);

    return 0;
}
```