#include <bits/stdc++.h>
using namespace std;

char s[3][2005];
int len[3],n,ans;
bool f[3][3][2005];
inline long long read()
{
	long long x=0,y=1;char ch=getchar();
	while (ch>'9'||ch<'0'){
		if (ch=='-')y=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*y;
}

inline bool check(int a,int b,int st){
	for (int i=1;i+st-1<=n;i++)
	if (s[a][st+i-1]!=s[b][i]&&s[a][st+i-1]!='?'&&s[b][i]!='?') return 0;
	return 1;
}
inline int cal(int a,int b,int c,int x,int y){
	if (n-x+1+n-y+1<=n) return min(len[a]-x+1,len[b])+min(len[b]-y+1,len[c]);
	if (f[a][c][x+y-1]) return min(len[a]-x+1,len[b])+min(max(len[b]-y+1,len[a]-(x+y-1)+1),len[c]);
	return 0;
}
int main()
{
	scanf("%s",s[0]+1);len[0]=strlen(s[0]+1);
	scanf("%s",s[1]+1);len[1]=strlen(s[1]+1);
	scanf("%s",s[2]+1);len[2]=strlen(s[2]+1);
	n=max(len[0],len[1]);
	n=max(len[2],n);
	for (int i=0;i<3;i++)
	for (int j=len[i]+1;j<=n;j++)
	s[i][j]='?';
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
	if (i!=j){
		for (int k=1;k<=n;k++)
		f[i][j][k]=check(i,j,k);
		f[i][j][n+1]=1;
	}
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
	if (i!=j){
		for (int k=1;k<=n+1;k++)
		if (f[i][j][k]){
			for (int h=1;h<=n+1;h++)
			if (f[j][3-i-j][h]) ans=max(ans,cal(i,j,3-i-j,k,h));
		}
	}
	printf("%d\n",len[0]+len[1]+len[2]-ans);
}

### 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 <bits/stdc++.h>
using namespace std;

char s[3][2005];
int len[3],n,ans;
bool f[3][3][2005];
inline long long read()
{
	long long x=0,y=1;char ch=getchar();
	while (ch>'9'||ch<'0'){
		if (ch=='-')y=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*y;
}

inline bool check(int a,int b,int st){
	for (int i=1;i+st-1<=n;i++)
	if (s[a][st+i-1]!=s[b][i]&&s[a][st+i-1]!='?'&&s[b][i]!='?') return 0;
	return 1;
}
inline int cal(int a,int b,int c,int x,int y){
	if (n-x+1+n-y+1<=n) return min(len[a]-x+1,len[b])+min(len[b]-y+1,len[c]);
	if (f[a][c][x+y-1]) return min(len[a]-x+1,len[b])+min(max(len[b]-y+1,len[a]-(x+y-1)+1),len[c]);
	return 0;
}
int main()
{
	scanf("%s",s[0]+1);len[0]=strlen(s[0]+1);
	scanf("%s",s[1]+1);len[1]=strlen(s[1]+1);
	scanf("%s",s[2]+1);len[2]=strlen(s[2]+1);
	n=max(len[0],len[1]);
	n=max(len[2],n);
	for (int i=0;i<3;i++)
	for (int j=len[i]+1;j<=n;j++)
	s[i][j]='?';
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
	if (i!=j){
		for (int k=1;k<=n;k++)
		f[i][j][k]=check(i,j,k);
		f[i][j][n+1]=1;
	}
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
	if (i!=j){
		for (int k=1;k<=n+1;k++)
		if (f[i][j][k]){
			for (int h=1;h<=n+1;h++)
			if (f[j][3-i-j][h]) ans=max(ans,cal(i,j,3-i-j,k,h));
		}
	}
	printf("%d\n",len[0]+len[1]+len[2]-ans);
}

```