#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int len[3],ans,lim,oth;
bool dp[3][3][2005];
char s[2][2005];
int lef(int x,int y)
{
	if(x!=0&&y!=0)return 0;
	if(x!=1&&y!=1)return 1;
	if(x!=2&&y!=2)return 2;
}
int main()
{
	scanf("%s%s%s",s[0]+1,s[1]+1,s[2]+1);
	for(int i=0;i<3;i++)len[i]=strlen(s[i]+1);
	ans=len[0]+len[1]+len[2];
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==j)continue;
			for(int k=1;k<=len[i];k++)
			{
				dp[i][j][k]=true;
				for(int u=k;u<=len[i]&&u-k+1<=len[j];u++)
				{
					if(s[i][u]=='?'||s[j][u-k+1]=='?'||s[i][u]==s[j][u-k+1])continue;
					dp[i][j][k]=false;
					break;
				}
			}
		}
	}
	bool o1,o2;
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==j)continue;
			oth=lef(i,j);
			for(int k=1;k<=len[i];k++)
			{
				if(!dp[i][j][k])continue;
				lim=max(len[i],len[j]+k-1);
				ans=min(ans,lim+len[oth]);
				for(int u=1;u<=lim;u++)
				{
					o1=true;o2=true;
					if(u<=len[i])o1=dp[i][oth][u];
					if(!(u+len[oth]-1<k||u>k+len[j]-1))
					{
						if(u<k)o2=dp[oth][j][k-u+1];
						else o2=dp[j][oth][u-k+1]; 
					}
					if(o1&&o2)ans=min(ans,max(lim,u+len[oth]-1));
				}
			}
		}
	}
	printf("%d\n",ans);
}
### Prompt

Please create a solution in CPP 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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int len[3],ans,lim,oth;
bool dp[3][3][2005];
char s[2][2005];
int lef(int x,int y)
{
	if(x!=0&&y!=0)return 0;
	if(x!=1&&y!=1)return 1;
	if(x!=2&&y!=2)return 2;
}
int main()
{
	scanf("%s%s%s",s[0]+1,s[1]+1,s[2]+1);
	for(int i=0;i<3;i++)len[i]=strlen(s[i]+1);
	ans=len[0]+len[1]+len[2];
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==j)continue;
			for(int k=1;k<=len[i];k++)
			{
				dp[i][j][k]=true;
				for(int u=k;u<=len[i]&&u-k+1<=len[j];u++)
				{
					if(s[i][u]=='?'||s[j][u-k+1]=='?'||s[i][u]==s[j][u-k+1])continue;
					dp[i][j][k]=false;
					break;
				}
			}
		}
	}
	bool o1,o2;
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==j)continue;
			oth=lef(i,j);
			for(int k=1;k<=len[i];k++)
			{
				if(!dp[i][j][k])continue;
				lim=max(len[i],len[j]+k-1);
				ans=min(ans,lim+len[oth]);
				for(int u=1;u<=lim;u++)
				{
					o1=true;o2=true;
					if(u<=len[i])o1=dp[i][oth][u];
					if(!(u+len[oth]-1<k||u>k+len[j]-1))
					{
						if(u<k)o2=dp[oth][j][k-u+1];
						else o2=dp[j][oth][u-k+1]; 
					}
					if(o1&&o2)ans=min(ans,max(lim,u+len[oth]-1));
				}
			}
		}
	}
	printf("%d\n",ans);
}
```