#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
ll INF = 6001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll N;

bool F(char a,char b){
    return (a == b || a == '?' || b == '?');
}

bool AB[100000];
bool AC[100000];
bool BC[100000];

int main(){
   string A,B,C;
   cin >> A >> B >> C;
   ll a = A.size(),b = B.size(),c = C.size();
   rep(i,a) rep(j,b) if(!F(A[i],B[j])) AB[50000+i-j] = true; 
   rep(i,a) rep(j,c) if(!F(A[i],C[j])) AC[50000+i-j] = true; 
   rep(i,b) rep(j,c) if(!F(B[i],C[j])) BC[50000+i-j] = true;
   ll ans = INF;
   FOR(i,-4000,4000) FOR(j,-4000,4000){
       if(!AB[50000+i] && !AC[50000+j] && !BC[50000+j-i]){
           ans = min(ans,max(b+i,max(c+j,a)) + max(0LL,max(-i,-j)));
       }
   }
   cout << ans << endl;
}
### Prompt

Please create a solution in cpp 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;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
ll INF = 6001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll N;

bool F(char a,char b){
    return (a == b || a == '?' || b == '?');
}

bool AB[100000];
bool AC[100000];
bool BC[100000];

int main(){
   string A,B,C;
   cin >> A >> B >> C;
   ll a = A.size(),b = B.size(),c = C.size();
   rep(i,a) rep(j,b) if(!F(A[i],B[j])) AB[50000+i-j] = true; 
   rep(i,a) rep(j,c) if(!F(A[i],C[j])) AC[50000+i-j] = true; 
   rep(i,b) rep(j,c) if(!F(B[i],C[j])) BC[50000+i-j] = true;
   ll ans = INF;
   FOR(i,-4000,4000) FOR(j,-4000,4000){
       if(!AB[50000+i] && !AC[50000+j] && !BC[50000+j-i]){
           ans = min(ans,max(b+i,max(c+j,a)) + max(0LL,max(-i,-j)));
       }
   }
   cout << ans << endl;
}
```