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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//end

constexpr int N=8000,M=4000;
string s,t,r;
bool st[16020]={},sr[16020]={},tr[16020]={};
bool check(char c,char d){return (c=='?'||d=='?'||c==d);}

int main(){
   cin>>s>>t>>r;
   int a=s.size(),b=t.size(),c=r.size();
   rep(i,0,a)rep(j,0,b)if(!check(s[i],t[j]))st[i-j+N]=1;
   rep(i,0,a)rep(j,0,c)if(!check(s[i],r[j]))sr[i-j+N]=1;
   rep(i,0,b)rep(j,0,c)if(!check(t[i],r[j]))tr[i-j+N]=1;
   int res=3*N;
   rep(i,-M,M+1)rep(j,-M,M+1)if(!st[i+N]&&!sr[j+N]&&!tr[j-i+N]){
      int lb=min({0,i,j}),rb=max({a,b+i,c+j});
      chmin(res,rb-lb);
   } printf("%d\n",res);
   return 0;
}
### 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
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//end

constexpr int N=8000,M=4000;
string s,t,r;
bool st[16020]={},sr[16020]={},tr[16020]={};
bool check(char c,char d){return (c=='?'||d=='?'||c==d);}

int main(){
   cin>>s>>t>>r;
   int a=s.size(),b=t.size(),c=r.size();
   rep(i,0,a)rep(j,0,b)if(!check(s[i],t[j]))st[i-j+N]=1;
   rep(i,0,a)rep(j,0,c)if(!check(s[i],r[j]))sr[i-j+N]=1;
   rep(i,0,b)rep(j,0,c)if(!check(t[i],r[j]))tr[i-j+N]=1;
   int res=3*N;
   rep(i,-M,M+1)rep(j,-M,M+1)if(!st[i+N]&&!sr[j+N]&&!tr[j-i+N]){
      int lb=min({0,i,j}),rb=max({a,b+i,c+j});
      chmin(res,rb-lb);
   } printf("%d\n",res);
   return 0;
}
```