#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

string a,b,c;
bool p1[40000],p2[40000],p3[40000];
bool*okab=&p1[20000],*okac=&p2[20000],*okbc=&p3[20000];

int main(){
	cin>>a>>b>>c;
	memset(p1,true,sizeof(p1));
	memset(p2,true,sizeof(p2));
	memset(p3,true,sizeof(p3));
	for(int i=-6000;i<=6000;i++){
		bool A=true,B=true,C=true;
		rep(j,a.size()){
			int k=j-i;
			if(0<=k&&k<b.size()&&a[j]!=b[k]&&a[j]!='?'&&b[k]!='?')A=false;
			if(0<=k&&k<c.size()&&a[j]!=c[k]&&a[j]!='?'&&c[k]!='?')B=false;
		}
		rep(j,b.size()){
			int k=j-i;
			if(0<=k&&k<c.size()&&b[j]!=c[k]&&b[j]!='?'&&c[k]!='?')C=false;
		}
		okab[i]=A;okac[i]=B;okbc[i]=C;
	}
	int Min=INT_MAX;
	for(int i=-5000;i<=5000;i++){
		for(int j=-5000;j<=5000;j++){
			if(okab[i]&&okac[j]&&okbc[j-i]){
				int l=min({0,i,j});
				int r=max({0+(int)a.size(),i+(int)b.size(),j+(int)c.size()});
				Min=min(Min,r-l);
			}
		}
	}
	cout<<Min<<endl;
}
### Prompt

Please formulate 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 rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

string a,b,c;
bool p1[40000],p2[40000],p3[40000];
bool*okab=&p1[20000],*okac=&p2[20000],*okbc=&p3[20000];

int main(){
	cin>>a>>b>>c;
	memset(p1,true,sizeof(p1));
	memset(p2,true,sizeof(p2));
	memset(p3,true,sizeof(p3));
	for(int i=-6000;i<=6000;i++){
		bool A=true,B=true,C=true;
		rep(j,a.size()){
			int k=j-i;
			if(0<=k&&k<b.size()&&a[j]!=b[k]&&a[j]!='?'&&b[k]!='?')A=false;
			if(0<=k&&k<c.size()&&a[j]!=c[k]&&a[j]!='?'&&c[k]!='?')B=false;
		}
		rep(j,b.size()){
			int k=j-i;
			if(0<=k&&k<c.size()&&b[j]!=c[k]&&b[j]!='?'&&c[k]!='?')C=false;
		}
		okab[i]=A;okac[i]=B;okbc[i]=C;
	}
	int Min=INT_MAX;
	for(int i=-5000;i<=5000;i++){
		for(int j=-5000;j<=5000;j++){
			if(okab[i]&&okac[j]&&okbc[j-i]){
				int l=min({0,i,j});
				int r=max({0+(int)a.size(),i+(int)b.size(),j+(int)c.size()});
				Min=min(Min,r-l);
			}
		}
	}
	cout<<Min<<endl;
}
```