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

#define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
using ll = long long;
const ll mod = 998244353;

void wt(string x, string y,vector<int>& lis){

  	//cout << x << y << endl;
    int xs = x.size();
    int ys = y.size();
  	
  
    rep(i,-ys,xs){
        int flag = 1;
        rep(j,max(0,i),min( xs , i+ys )){
          	//cout << j << " " << j-i << endl;
            if ((x.at(j) != y.at(j-i)) && (x.at(j)!='?') && (y.at(j-i)!='?')){
                flag = 0;
             
                break;
            } 
        }

        lis.at(i+15000) = flag;
    }

    return;
}

int main(){

    vector<int> ab(30000,1); //0は15000とする
    vector<int> ac(30000,1);
    vector<int> bc(30000,1);

    string a,b,c;
    cin >> a >> b >> c;

    wt(a,b,ab);
    wt(a,c,ac);
    wt(b,c,bc);

    int ans = 100000;
    int as = a.size();
    int bs = b.size();
    int cs = c.size();

    rep(i,-4100,4100){
        rep(j,-4100,4100){
            if ((ab[i+15000] & ac[j+15000]) & bc[j-i+15000]){
                ans = min(ans , max(max(as,bs+i),cs+j) - min(min(0,i),j) );
            }
        }
    }

    cout << ans << endl;


}
### 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

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

#define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
using ll = long long;
const ll mod = 998244353;

void wt(string x, string y,vector<int>& lis){

  	//cout << x << y << endl;
    int xs = x.size();
    int ys = y.size();
  	
  
    rep(i,-ys,xs){
        int flag = 1;
        rep(j,max(0,i),min( xs , i+ys )){
          	//cout << j << " " << j-i << endl;
            if ((x.at(j) != y.at(j-i)) && (x.at(j)!='?') && (y.at(j-i)!='?')){
                flag = 0;
             
                break;
            } 
        }

        lis.at(i+15000) = flag;
    }

    return;
}

int main(){

    vector<int> ab(30000,1); //0は15000とする
    vector<int> ac(30000,1);
    vector<int> bc(30000,1);

    string a,b,c;
    cin >> a >> b >> c;

    wt(a,b,ab);
    wt(a,c,ac);
    wt(b,c,bc);

    int ans = 100000;
    int as = a.size();
    int bs = b.size();
    int cs = c.size();

    rep(i,-4100,4100){
        rep(j,-4100,4100){
            if ((ab[i+15000] & ac[j+15000]) & bc[j-i+15000]){
                ans = min(ans , max(max(as,bs+i),cs+j) - min(min(0,i),j) );
            }
        }
    }

    cout << ans << endl;


}
```