#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
char s[3][N];
int ok[3][3][N], len[3]; // s[x].suffix = s[y].prefix 
int solve(int a,int b,int c) {
	int tot=len[a]+len[b]+len[c],ans=1e9;
	for(int x=0;x<=len[a];x++){
		if(ok[a][b][x]==0)continue;
		for(int y=0;y<=2000;y++){
			if(y<=len[b]&&ok[b][c][y]==0)continue;
			if(1+x+y<=len[a]&&ok[a][c][x+y]==0)continue;
			ans=min(ans, max(max(len[a],1+x+len[b]-1),1+x+y+len[c]-1));
			//printf("x=%d,y=%d\n", x,y);
			// [1, len[a]]
			// 	[1+x, x+len[b]]
			// 	 [1+x+y, x+y+len[c]]
		}
	}
	return ans;
}
int main() {
	for(int i=0;i<3;i++) {
		scanf("%s", s[i]+1);
		len[i] = strlen(s[i]+1);
	}
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++){
			if (i==j) continue;
			int tmp=len[i];
			for(int x=0;x<=tmp;x++){
				bool flag=1;
				int p1=1+x, p2=1;
				while(1){
					if(p1>len[i]||p2>len[j])break;
					if(s[i][p1]!=s[j][p2]&&s[i][p1]!='?'&&s[j][p2]!='?'){
						flag=0; break;
					}
					p1++; p2++;
				}
				if(flag) ok[i][j][x]=1;
			}
		}
	}

	int ans=1e9;
	ans=min(ans,solve(0,1,2));
	ans=min(ans,solve(0,2,1));
	ans=min(ans,solve(1,0,2));
	ans=min(ans,solve(1,2,0));
	ans=min(ans,solve(2,0,1));
	ans=min(ans,solve(2,1,0));
	cout<<ans<<endl;
}
### Prompt

Your task is to create a Cpp solution 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 <bits/stdc++.h>
using namespace std;
const int N = 4005;
char s[3][N];
int ok[3][3][N], len[3]; // s[x].suffix = s[y].prefix 
int solve(int a,int b,int c) {
	int tot=len[a]+len[b]+len[c],ans=1e9;
	for(int x=0;x<=len[a];x++){
		if(ok[a][b][x]==0)continue;
		for(int y=0;y<=2000;y++){
			if(y<=len[b]&&ok[b][c][y]==0)continue;
			if(1+x+y<=len[a]&&ok[a][c][x+y]==0)continue;
			ans=min(ans, max(max(len[a],1+x+len[b]-1),1+x+y+len[c]-1));
			//printf("x=%d,y=%d\n", x,y);
			// [1, len[a]]
			// 	[1+x, x+len[b]]
			// 	 [1+x+y, x+y+len[c]]
		}
	}
	return ans;
}
int main() {
	for(int i=0;i<3;i++) {
		scanf("%s", s[i]+1);
		len[i] = strlen(s[i]+1);
	}
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++){
			if (i==j) continue;
			int tmp=len[i];
			for(int x=0;x<=tmp;x++){
				bool flag=1;
				int p1=1+x, p2=1;
				while(1){
					if(p1>len[i]||p2>len[j])break;
					if(s[i][p1]!=s[j][p2]&&s[i][p1]!='?'&&s[j][p2]!='?'){
						flag=0; break;
					}
					p1++; p2++;
				}
				if(flag) ok[i][j][x]=1;
			}
		}
	}

	int ans=1e9;
	ans=min(ans,solve(0,1,2));
	ans=min(ans,solve(0,2,1));
	ans=min(ans,solve(1,0,2));
	ans=min(ans,solve(1,2,0));
	ans=min(ans,solve(2,0,1));
	ans=min(ans,solve(2,1,0));
	cout<<ans<<endl;
}
```