#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int t=1e4;
bool f[3][3][20000];
string s[3]; 
int l[3];
bool check(char a,char b){
	RE (a=='?'||b=='?'||a==b);
}
void solve(int a,int b){
	rep(i,0,l[a])
		rep(j,0,l[b])
			if(!check(s[a][i],s[b][j]))f[a][b][t+i-j]=1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	rep(i,0,3){
		cin>>s[i];l[i]=s[i].size();
	}
	solve(0,1);solve(0,2);solve(1,2);
	int ans=l[0]+l[1]+l[2];
	FOR(i,-4000,4000)
		FOR(j,-4000,4000)
			if(!f[0][1][i+t]&&!f[0][2][j+t]&&!f[1][2][t+j-i])
				gmin(ans,max(l[0],max(l[1]+i,j+l[2]))-min(0,min(i,j)));
	cout<<ans;
	RE 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
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int t=1e4;
bool f[3][3][20000];
string s[3]; 
int l[3];
bool check(char a,char b){
	RE (a=='?'||b=='?'||a==b);
}
void solve(int a,int b){
	rep(i,0,l[a])
		rep(j,0,l[b])
			if(!check(s[a][i],s[b][j]))f[a][b][t+i-j]=1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	rep(i,0,3){
		cin>>s[i];l[i]=s[i].size();
	}
	solve(0,1);solve(0,2);solve(1,2);
	int ans=l[0]+l[1]+l[2];
	FOR(i,-4000,4000)
		FOR(j,-4000,4000)
			if(!f[0][1][i+t]&&!f[0][2][j+t]&&!f[1][2][t+j-i])
				gmin(ans,max(l[0],max(l[1]+i,j+l[2]))-min(0,min(i,j)));
	cout<<ans;
	RE 0;
}



```