#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=2010;
const int t=15000;
int n,m,k,ans;
bool ac[3*t],ab[3*t],bc[3*t];
char a[maxn],b[maxn],c[maxn];
inline bool ok(char aa,char bb)
{
	if (aa==bb ||aa=='?' || bb=='?') return 1;
return 0;
}
int main()
{
	scanf("%s%s%s",a+1,b+1,c+1); ans=3*maxn;
	n=strlen(a+1); m=strlen(b+1); k=strlen(c+1);
	memset(ac,1,sizeof ac); memset(ab,1,sizeof ab); memset(bc,1,sizeof bc);
	for (int i=1;i<=n;++i)
	 for (int j=1;j<=m;++j) if (!ok(a[i],b[j])) ab[i-j+t]=0;
	for (int i=1;i<=n;++i)
	 for (int j=1;j<=k;++j) if (!ok(a[i],c[j])) ac[i-j+t]=0;
	for (int i=1;i<=m;++i)
	 for (int j=1;j<=k;++j) if (!ok(b[i],c[j])) bc[i-j+t]=0;
	for (int i=-4010;i<=4010;++i)
	 for (int j=-4010;j<=4010;++j)
	 if (ab[t-(1-i)] && ac[t-(1-j)] && bc[t-(i-j)])
	 {
	 	int l=min(1,min(i,j)),r=max(n,max(i+m-1,j+k-1));
	 	ans=min(ans,r-l+1);
	 }
	printf("%d\n",ans);
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 <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=2010;
const int t=15000;
int n,m,k,ans;
bool ac[3*t],ab[3*t],bc[3*t];
char a[maxn],b[maxn],c[maxn];
inline bool ok(char aa,char bb)
{
	if (aa==bb ||aa=='?' || bb=='?') return 1;
return 0;
}
int main()
{
	scanf("%s%s%s",a+1,b+1,c+1); ans=3*maxn;
	n=strlen(a+1); m=strlen(b+1); k=strlen(c+1);
	memset(ac,1,sizeof ac); memset(ab,1,sizeof ab); memset(bc,1,sizeof bc);
	for (int i=1;i<=n;++i)
	 for (int j=1;j<=m;++j) if (!ok(a[i],b[j])) ab[i-j+t]=0;
	for (int i=1;i<=n;++i)
	 for (int j=1;j<=k;++j) if (!ok(a[i],c[j])) ac[i-j+t]=0;
	for (int i=1;i<=m;++i)
	 for (int j=1;j<=k;++j) if (!ok(b[i],c[j])) bc[i-j+t]=0;
	for (int i=-4010;i<=4010;++i)
	 for (int j=-4010;j<=4010;++j)
	 if (ab[t-(1-i)] && ac[t-(1-j)] && bc[t-(i-j)])
	 {
	 	int l=min(1,min(i,j)),r=max(n,max(i+m-1,j+k-1));
	 	ans=min(ans,r-l+1);
	 }
	printf("%d\n",ans);
return 0;
}
```