#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

int solve(string a,string b,string c){
	auto build=[](string x,string y){
		int nx=x.length(),ny=y.length();
		vector<bool> flag(nx+1,true);
		rep(i,nx+1){
			rep(j,ny){
				if(i+j>=nx) break;
				if(x[i+j]!='?' && y[j]!='?' && x[i+j]!=y[j]){ flag[i]=false; break; }
			}
		}
		return flag;
	};

	int na=a.length(),nb=b.length(),nc=c.length();
	vector<bool> flag_ab=build(a,b);
	vector<bool> flag_ac=build(a,c);
	vector<bool> flag_bc=build(b,c);
	vector<bool> flag_cb=build(c,b);

	int res=INF;
	rep(i,na+1) if(flag_ab[i]) {
		rep(j,na+1) if(flag_ac[j]) {
			if(j<=i && i-j<=nc && flag_cb[i-j]) res=min(res,max({na,i+nb,j+nc}));
			if(j>=i){
				if((j-i<=nb && flag_bc[j-i]) || j-i>=nb) res=min(res,max({na,i+nb,j+nc}));
			}
		}
		for(int j=na;j<=i+nb;j++){
			if(flag_bc[j-i]) res=min(res,max(i+nb,j+nc));
		}
	}
	rep(i,na+1) if(flag_ac[i]) {
		rep(j,na+1) if(flag_ab[j]) {
			if(j<=i && i-j<=nb && flag_bc[i-j]) res=min(res,max({na,i+nc,j+nb}));
			if(j>=i){
				if((j-i<=nc && flag_cb[j-i]) || j-i>=nc) res=min(res,max({na,i+nc,j+nb}));
			}
		}
		for(int j=na;j<=i+nc;j++){
			if(flag_cb[j-i]) res=min(res,max(i+nc,j+nb));
		}
	}
	return res;
}

int main(){
	string a,b,c; cin>>a>>b>>c;
	cout<<min({solve(a,b,c),solve(b,c,a),solve(c,a,b)})<<'\n';
	return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;

const int INF=1<<29;

int solve(string a,string b,string c){
	auto build=[](string x,string y){
		int nx=x.length(),ny=y.length();
		vector<bool> flag(nx+1,true);
		rep(i,nx+1){
			rep(j,ny){
				if(i+j>=nx) break;
				if(x[i+j]!='?' && y[j]!='?' && x[i+j]!=y[j]){ flag[i]=false; break; }
			}
		}
		return flag;
	};

	int na=a.length(),nb=b.length(),nc=c.length();
	vector<bool> flag_ab=build(a,b);
	vector<bool> flag_ac=build(a,c);
	vector<bool> flag_bc=build(b,c);
	vector<bool> flag_cb=build(c,b);

	int res=INF;
	rep(i,na+1) if(flag_ab[i]) {
		rep(j,na+1) if(flag_ac[j]) {
			if(j<=i && i-j<=nc && flag_cb[i-j]) res=min(res,max({na,i+nb,j+nc}));
			if(j>=i){
				if((j-i<=nb && flag_bc[j-i]) || j-i>=nb) res=min(res,max({na,i+nb,j+nc}));
			}
		}
		for(int j=na;j<=i+nb;j++){
			if(flag_bc[j-i]) res=min(res,max(i+nb,j+nc));
		}
	}
	rep(i,na+1) if(flag_ac[i]) {
		rep(j,na+1) if(flag_ab[j]) {
			if(j<=i && i-j<=nb && flag_bc[i-j]) res=min(res,max({na,i+nc,j+nb}));
			if(j>=i){
				if((j-i<=nc && flag_cb[j-i]) || j-i>=nc) res=min(res,max({na,i+nc,j+nb}));
			}
		}
		for(int j=na;j<=i+nc;j++){
			if(flag_cb[j-i]) res=min(res,max(i+nc,j+nb));
		}
	}
	return res;
}

int main(){
	string a,b,c; cin>>a>>b>>c;
	cout<<min({solve(a,b,c),solve(b,c,a),solve(c,a,b)})<<'\n';
	return 0;
}

```