#include<bits/stdc++.h>
#define ll long long
const int mod=1e9+7;
const int maxn=1e5;
using namespace std;
string s1,s2,s3;

bool ab[maxn],ac[maxn],bc[maxn];

bool match(char c1,char c2)
{
    return (c1=='?'||c2=='?'||c1==c2);
}
int main()
{
    //freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>s1>>s2>>s3;

    int A=s1.size();
    int B=s2.size();
    int C=s3.size();
    for(int i=0; i<A; i++)
        for(int j=0; j<B; j++)
            if(!match(s1[i],s2[j]))
            {
                ab[i-j+50000]=true;
                //cout<<i-j<<endl;
            }
            //cout<<endl;
    for(int i=0; i<B; i++)
        for(int j=0; j<C; j++)
            if(!match(s2[i],s3[j]))
            {
                bc[i-j+50000]=true;
                //cout<<i-j<<endl;
            }
            //cout<<endl;

    for(int i=0; i<A; i++)
        for(int j=0; j<C; j++)
            if(!match(s1[i],s3[j]))
            {
                ac[i-j+50000]=true;
                //cout<<i-j<<endl;
            }


    int ans=6000;
    for(int i=-4000; i<=4000; i++)
        for(int j=-4000; j<=4000; j++)
            if(!ab[i+50000]&&!bc[j-i+50000]&&!ac[j+50000])
            {
                int L=min(0,min(i,j));
                int R=max(A,max(B+i,C+j));
                ans=min(ans,R-L);
                //cout<<ans;
            }
    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>
#define ll long long
const int mod=1e9+7;
const int maxn=1e5;
using namespace std;
string s1,s2,s3;

bool ab[maxn],ac[maxn],bc[maxn];

bool match(char c1,char c2)
{
    return (c1=='?'||c2=='?'||c1==c2);
}
int main()
{
    //freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>s1>>s2>>s3;

    int A=s1.size();
    int B=s2.size();
    int C=s3.size();
    for(int i=0; i<A; i++)
        for(int j=0; j<B; j++)
            if(!match(s1[i],s2[j]))
            {
                ab[i-j+50000]=true;
                //cout<<i-j<<endl;
            }
            //cout<<endl;
    for(int i=0; i<B; i++)
        for(int j=0; j<C; j++)
            if(!match(s2[i],s3[j]))
            {
                bc[i-j+50000]=true;
                //cout<<i-j<<endl;
            }
            //cout<<endl;

    for(int i=0; i<A; i++)
        for(int j=0; j<C; j++)
            if(!match(s1[i],s3[j]))
            {
                ac[i-j+50000]=true;
                //cout<<i-j<<endl;
            }


    int ans=6000;
    for(int i=-4000; i<=4000; i++)
        for(int j=-4000; j<=4000; j++)
            if(!ab[i+50000]&&!bc[j-i+50000]&&!ac[j+50000])
            {
                int L=min(0,min(i,j));
                int R=max(A,max(B+i,C+j));
                ans=min(ans,R-L);
                //cout<<ans;
            }
    cout<<ans<<endl;

}


```