#include <bits/stdc++.h>
using namespace std;

const int MAX_N=1e4+10;

vector<int> connpos(const string &s,const string &t){
    vector<int> res(MAX_N,1);
    for (int i=0;i<s.size();++i)
        for (int j=0;i+j<s.size()&&j<t.size();++j)
            if (!(s[i+j]==t[j]||s[i+j]=='?'||t[j]=='?')) res[i]=0;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<string> S(3);
    vector<int> n(3);
    for (int i=0;i<3;++i) cin >> S[i],n[i]=S[i].size();
    vector<int> perm(3);
    iota(perm.begin(),perm.end(),0);
    int ans=MAX_N;
    do {
        vector<int> ab=connpos(S[perm[0]],S[perm[1]])
                    ,bc=connpos(S[perm[1]],S[perm[2]])
                    ,ac=connpos(S[perm[0]],S[perm[2]]);
        for (int i=0;i<=n[perm[0]];++i)
            for (int j=0;j<=max(n[perm[0]],n[perm[1]]);++j)
                if (ab[i]&&bc[j]&&ac[i+j])
                    ans=min(ans,max({n[perm[0]],i+n[perm[1]],i+j+n[perm[2]]}));
    } while(next_permutation(perm.begin(),perm.end()));
    cout << ans << '\n';
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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>
using namespace std;

const int MAX_N=1e4+10;

vector<int> connpos(const string &s,const string &t){
    vector<int> res(MAX_N,1);
    for (int i=0;i<s.size();++i)
        for (int j=0;i+j<s.size()&&j<t.size();++j)
            if (!(s[i+j]==t[j]||s[i+j]=='?'||t[j]=='?')) res[i]=0;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<string> S(3);
    vector<int> n(3);
    for (int i=0;i<3;++i) cin >> S[i],n[i]=S[i].size();
    vector<int> perm(3);
    iota(perm.begin(),perm.end(),0);
    int ans=MAX_N;
    do {
        vector<int> ab=connpos(S[perm[0]],S[perm[1]])
                    ,bc=connpos(S[perm[1]],S[perm[2]])
                    ,ac=connpos(S[perm[0]],S[perm[2]]);
        for (int i=0;i<=n[perm[0]];++i)
            for (int j=0;j<=max(n[perm[0]],n[perm[1]]);++j)
                if (ab[i]&&bc[j]&&ac[i+j])
                    ans=min(ans,max({n[perm[0]],i+n[perm[1]],i+j+n[perm[2]]}));
    } while(next_permutation(perm.begin(),perm.end()));
    cout << ans << '\n';
}

```