#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define PER(a,b,c) for(int a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
using namespace std;
const int MAXN=1e6+5;
int n,m,t;
char a[MAXN],b[MAXN],c[MAXN];
int ab[MAXN],bc[MAXN],ac[MAXN];
int o=1e4;
int check(char x,char y){
    return x=='?'||y=='?'||x==y;
}
int main(){
    cin>>a+1>>b+1>>c+1;
    int la=strlen(a+1),lb=strlen(b+1),lc=strlen(c+1);
    REP(i,-4000,4000)ab[i+o]=ac[i+o]=bc[i+o]=1;
    REP(i,1,la)REP(j,1,lb){
        if(!check(a[i],b[j]))ab[i-j+o]=0;
    }
    REP(i,1,la)REP(j,1,lc){
        if(!check(a[i],c[j]))ac[i-j+o]=0;
    }
    REP(i,1,lb)REP(j,1,lc){
        if(!check(b[i],c[j]))bc[i-j+o]=0;
    }
    int ans=la+lb+lc;
    REP(i,-4000,4000)REP(j,-4000,4000){
        if(ab[i+o]&&ac[j+o]&&bc[j-i+o]){
            ans=min(ans,max(la,max(i+lb,j+lc))-min(1,min(1+i,1+j))+1);
        }
    }
    cout<<ans;
}
### Prompt

Create a solution in Cpp for 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<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define PER(a,b,c) for(int a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
using namespace std;
const int MAXN=1e6+5;
int n,m,t;
char a[MAXN],b[MAXN],c[MAXN];
int ab[MAXN],bc[MAXN],ac[MAXN];
int o=1e4;
int check(char x,char y){
    return x=='?'||y=='?'||x==y;
}
int main(){
    cin>>a+1>>b+1>>c+1;
    int la=strlen(a+1),lb=strlen(b+1),lc=strlen(c+1);
    REP(i,-4000,4000)ab[i+o]=ac[i+o]=bc[i+o]=1;
    REP(i,1,la)REP(j,1,lb){
        if(!check(a[i],b[j]))ab[i-j+o]=0;
    }
    REP(i,1,la)REP(j,1,lc){
        if(!check(a[i],c[j]))ac[i-j+o]=0;
    }
    REP(i,1,lb)REP(j,1,lc){
        if(!check(b[i],c[j]))bc[i-j+o]=0;
    }
    int ans=la+lb+lc;
    REP(i,-4000,4000)REP(j,-4000,4000){
        if(ab[i+o]&&ac[j+o]&&bc[j-i+o]){
            ans=min(ans,max(la,max(i+lb,j+lc))-min(1,min(1+i,1+j))+1);
        }
    }
    cout<<ans;
}
```