#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 2010
using namespace std;
char a[maxn],b[maxn],c[maxn];
bool ab[maxn+maxn+maxn+maxn+maxn],ac[5*maxn],bc[5*maxn];//bca,cba,abc,acb
int match(char a,char b){
	if(a==b||a=='?'||b=='?')return 1;
	return 0;
}
int main(){
	int i,j,A,B,C,L,R,ans=5*maxn;
	scanf("%s%s%s",a,b,c);
	A=strlen(a),B=strlen(b),C=strlen(c);
	for(i=0;i<A;i++)
		for(j=0;j<B;j++)
			if(!match(a[i],b[j]))ab[i-j+2*maxn]=1;//标记不匹配位置
	for(i=0;i<A;i++)
		for(j=0;j<C;j++)
			if(!match(a[i],c[j]))ac[i-j+2*maxn]=1;
	for(i=0;i<B;i++)
		for(j=0;j<C;j++)
			if(!match(b[i],c[j]))bc[i-j+2*maxn]=1;
	for(i=-(B+C);i<=A+max(B,C);i++)//i记录b串首字母相对a串位置
		for(j=-(B+C);j<=A+max(B,C);j++)//j记录c串首字母相对a串位置
			if(!ab[i+2*maxn]&&!ac[j+2*maxn]&&!bc[j-i+2*maxn]){//j-i记录c串首字母相对b串位置
				L=min(0,min(i,j)),R=max(A,max(B+i,C+j));//min(i,j)>0表示在a串内部匹配，故取0;B+i,或C+j可能还小于A
				ans=min(ans,R-L);
			}
	printf("%d\n",ans);
	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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 2010
using namespace std;
char a[maxn],b[maxn],c[maxn];
bool ab[maxn+maxn+maxn+maxn+maxn],ac[5*maxn],bc[5*maxn];//bca,cba,abc,acb
int match(char a,char b){
	if(a==b||a=='?'||b=='?')return 1;
	return 0;
}
int main(){
	int i,j,A,B,C,L,R,ans=5*maxn;
	scanf("%s%s%s",a,b,c);
	A=strlen(a),B=strlen(b),C=strlen(c);
	for(i=0;i<A;i++)
		for(j=0;j<B;j++)
			if(!match(a[i],b[j]))ab[i-j+2*maxn]=1;//标记不匹配位置
	for(i=0;i<A;i++)
		for(j=0;j<C;j++)
			if(!match(a[i],c[j]))ac[i-j+2*maxn]=1;
	for(i=0;i<B;i++)
		for(j=0;j<C;j++)
			if(!match(b[i],c[j]))bc[i-j+2*maxn]=1;
	for(i=-(B+C);i<=A+max(B,C);i++)//i记录b串首字母相对a串位置
		for(j=-(B+C);j<=A+max(B,C);j++)//j记录c串首字母相对a串位置
			if(!ab[i+2*maxn]&&!ac[j+2*maxn]&&!bc[j-i+2*maxn]){//j-i记录c串首字母相对b串位置
				L=min(0,min(i,j)),R=max(A,max(B+i,C+j));//min(i,j)>0表示在a串内部匹配，故取0;B+i,或C+j可能还小于A
				ans=min(ans,R-L);
			}
	printf("%d\n",ans);
	return 0;
}
```