// <head>
    #include <bits/stdc++.h>
    #define rep(i,n) for(int i=0;i<(int)(n);i++)
    using namespace std;
    using ll = long long;
    const int INF = 1002003004;
    const ll LINF = 1002003004005006007ll;
    struct preprocess{preprocess()
    {cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}}____;
// </head>

// <library>
    
// </library>

bool match(char &c1, char &c2){
    return (c1==c2 || c1=='?' || c2 == '?');
}

int main(){
    string a,b,c; cin >> a >> b >> c;
    const int MX = 4005;
    const int bias = 30000;
    vector<bool> ab(MX+bias,true);
    vector<bool> bc(MX+bias,true);
    vector<bool> ac(MX+bias,true);
    int la = a.size(), lb = b.size(), lc = c.size();
    rep(i,la) rep(j,lb) if(!match(a[i],b[j])) ab[i-j+bias] = false;
    rep(i,la) rep(j,lc) if(!match(a[i],c[j])) ac[i-j+bias] = false;
    rep(i,lb) rep(j,lc) if(!match(b[i],c[j])) bc[i-j+bias] = false;
    int ans = INF;
    for (int i = -MX; i < MX; i++){
        for (int j = -MX; j < MX; j++){
            if(ab[i+bias]&&ac[j+bias]&&bc[j-i+bias]){
                int l = min(i,min(j,0));
                int r = max(i+lb,max(j+lc,la));
                ans = min(ans, r-l);
                
            }
            
        }
        
    }
    cout << ans << '\n';
    
}
### Prompt

Generate 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
// <head>
    #include <bits/stdc++.h>
    #define rep(i,n) for(int i=0;i<(int)(n);i++)
    using namespace std;
    using ll = long long;
    const int INF = 1002003004;
    const ll LINF = 1002003004005006007ll;
    struct preprocess{preprocess()
    {cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}}____;
// </head>

// <library>
    
// </library>

bool match(char &c1, char &c2){
    return (c1==c2 || c1=='?' || c2 == '?');
}

int main(){
    string a,b,c; cin >> a >> b >> c;
    const int MX = 4005;
    const int bias = 30000;
    vector<bool> ab(MX+bias,true);
    vector<bool> bc(MX+bias,true);
    vector<bool> ac(MX+bias,true);
    int la = a.size(), lb = b.size(), lc = c.size();
    rep(i,la) rep(j,lb) if(!match(a[i],b[j])) ab[i-j+bias] = false;
    rep(i,la) rep(j,lc) if(!match(a[i],c[j])) ac[i-j+bias] = false;
    rep(i,lb) rep(j,lc) if(!match(b[i],c[j])) bc[i-j+bias] = false;
    int ans = INF;
    for (int i = -MX; i < MX; i++){
        for (int j = -MX; j < MX; j++){
            if(ab[i+bias]&&ac[j+bias]&&bc[j-i+bias]){
                int l = min(i,min(j,0));
                int r = max(i+lb,max(j+lc,la));
                ans = min(ans, r-l);
                
            }
            
        }
        
    }
    cout << ans << '\n';
    
}
```