#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
char s[3][2005];
int out[3][5005], len[3], ans = 6000;
int main(){
	rep(i,3){
		scanf("%s", s[i]);
		len[i] = strlen(s[i]);
	}
	rep(u,3){
		int i = u == 0 ? 1 : 0, j = u == 2 ? 1 : 2;
		rep(k,len[i]) rep(l,len[j]) if(s[i][k] != '?' && s[j][l] != '?' && s[i][k] != s[j][l]){
			out[u][k-l+2500] = true;
		}
	}
	for(int i=-4000; i<=4000; i++) for(int j=-4000; j<=4000; j++){
		bool ok = true;
		if(-len[1] < i && i < len[0] && out[2][i+2500]) ok = false;
		if(-len[2] < j && j < len[0] && out[1][j+2500]) ok = false;
		if(-len[2] < j-i && j-i < len[1] && out[0][j-i+2500]) ok = false;
		if(ok) ans = min(ans, max({len[0],i+len[1],j+len[2]}) - min({0,i,j}));
	}
	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 <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
char s[3][2005];
int out[3][5005], len[3], ans = 6000;
int main(){
	rep(i,3){
		scanf("%s", s[i]);
		len[i] = strlen(s[i]);
	}
	rep(u,3){
		int i = u == 0 ? 1 : 0, j = u == 2 ? 1 : 2;
		rep(k,len[i]) rep(l,len[j]) if(s[i][k] != '?' && s[j][l] != '?' && s[i][k] != s[j][l]){
			out[u][k-l+2500] = true;
		}
	}
	for(int i=-4000; i<=4000; i++) for(int j=-4000; j<=4000; j++){
		bool ok = true;
		if(-len[1] < i && i < len[0] && out[2][i+2500]) ok = false;
		if(-len[2] < j && j < len[0] && out[1][j+2500]) ok = false;
		if(-len[2] < j-i && j-i < len[1] && out[0][j-i+2500]) ok = false;
		if(ok) ans = min(ans, max({len[0],i+len[1],j+len[2]}) - min({0,i,j}));
	}
	printf("%d\n", ans);
}
```