#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)

int main() {
    // your code goes here
    char a[5][2005];
    ll l[5],r[5]={0},ans=100000000;
    bool z[5015][5][5]={0};
    cin >> a[0] >> a[1] >> a[2];
    rep(i,0,2) l[i]=strlen(a[i]);
    rep(i,0,2){
        rep(j,0,2){
            if(i==j) continue;
            rep(k,0,l[i]-1){
                bool memo=true;
                rep(s,0,min(l[j]-1ll,l[i]-k-1)){
                    if(a[i][k+s]=='?') continue;
                    if(a[j][s]=='?') continue;
                    if(a[i][k+s]!=a[j][s]) memo=false;
                }
                if(memo) z[k][i][j]=true;
                //if(memo) cout << i << " " << j << " " << k << endl;
            }
            rep(k,l[i],5000) z[k][i][j]=true;
        }
    }
    vector<ll> p;
    p.push_back(0); p.push_back(1); p.push_back(2);
    do {
        rep(i,0,3*l[p[0]]){
            rep(j,0,min(3ll*l[p[1]],4500ll-i)){
                if(z[i][p[0]][p[1]]&&z[j][p[1]][p[2]]&&z[i+j][p[0]][p[2]]){
                    ll mm=max(l[p[0]],max(i+l[p[1]],i+j+l[p[2]]));
                    ans=min(ans,mm);
                }
            }
        }
    } while (next_permutation(p.begin(),p.end()));
    cout << ans << endl;
    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)

int main() {
    // your code goes here
    char a[5][2005];
    ll l[5],r[5]={0},ans=100000000;
    bool z[5015][5][5]={0};
    cin >> a[0] >> a[1] >> a[2];
    rep(i,0,2) l[i]=strlen(a[i]);
    rep(i,0,2){
        rep(j,0,2){
            if(i==j) continue;
            rep(k,0,l[i]-1){
                bool memo=true;
                rep(s,0,min(l[j]-1ll,l[i]-k-1)){
                    if(a[i][k+s]=='?') continue;
                    if(a[j][s]=='?') continue;
                    if(a[i][k+s]!=a[j][s]) memo=false;
                }
                if(memo) z[k][i][j]=true;
                //if(memo) cout << i << " " << j << " " << k << endl;
            }
            rep(k,l[i],5000) z[k][i][j]=true;
        }
    }
    vector<ll> p;
    p.push_back(0); p.push_back(1); p.push_back(2);
    do {
        rep(i,0,3*l[p[0]]){
            rep(j,0,min(3ll*l[p[1]],4500ll-i)){
                if(z[i][p[0]][p[1]]&&z[j][p[1]][p[2]]&&z[i+j][p[0]][p[2]]){
                    ll mm=max(l[p[0]],max(i+l[p[1]],i+j+l[p[2]]));
                    ans=min(ans,mm);
                }
            }
        }
    } while (next_permutation(p.begin(),p.end()));
    cout << ans << endl;
    return 0;
}
```