#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define Maxn 2010
#define Maxm 10010

char a[Maxn], b[Maxn], c[Maxn];
bool Cmp_ab[Maxm], Cmp_ac[Maxm], Cmp_bc[Maxm];

inline bool Compare(char x, char y) { return ((x == y) || (x == '?') || (y == '?')); }

int main()
{
	scanf("%s", a); int l_a = strlen(a);
	scanf("%s", b); int l_b = strlen(b);
	scanf("%s", c); int l_c = strlen(c);
	
	for (int i=0; i<l_a; i++) for (int j=0; j<l_b; j++) if (!Compare(a[i], b[j])) Cmp_ab[i - j + 4000] = 1;
	for (int i=0; i<l_a; i++) for (int j=0; j<l_c; j++) if (!Compare(a[i], c[j])) Cmp_ac[i - j + 4000] = 1;
	for (int i=0; i<l_b; i++) for (int j=0; j<l_c; j++) if (!Compare(b[i], c[j])) Cmp_bc[i - j + 4000] = 1;
	
	int Res = INF;
	for (int i=-4000; i<=4000; i++)
		for (int j=-4000; j<=4000; j++)
			if ((!Cmp_ab[i + 4000]) && (!Cmp_ac[j + 4000]) && (!Cmp_bc[j - i + 4000]))
				Res = min(Res, max(l_a, max(l_c + j, l_b + i)) - min(0, min(i, j)));
				
	printf("%d\n", Res);
}
### 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 INF 1000000000
#define Maxn 2010
#define Maxm 10010

char a[Maxn], b[Maxn], c[Maxn];
bool Cmp_ab[Maxm], Cmp_ac[Maxm], Cmp_bc[Maxm];

inline bool Compare(char x, char y) { return ((x == y) || (x == '?') || (y == '?')); }

int main()
{
	scanf("%s", a); int l_a = strlen(a);
	scanf("%s", b); int l_b = strlen(b);
	scanf("%s", c); int l_c = strlen(c);
	
	for (int i=0; i<l_a; i++) for (int j=0; j<l_b; j++) if (!Compare(a[i], b[j])) Cmp_ab[i - j + 4000] = 1;
	for (int i=0; i<l_a; i++) for (int j=0; j<l_c; j++) if (!Compare(a[i], c[j])) Cmp_ac[i - j + 4000] = 1;
	for (int i=0; i<l_b; i++) for (int j=0; j<l_c; j++) if (!Compare(b[i], c[j])) Cmp_bc[i - j + 4000] = 1;
	
	int Res = INF;
	for (int i=-4000; i<=4000; i++)
		for (int j=-4000; j<=4000; j++)
			if ((!Cmp_ab[i + 4000]) && (!Cmp_ac[j + 4000]) && (!Cmp_bc[j - i + 4000]))
				Res = min(Res, max(l_a, max(l_c + j, l_b + i)) - min(0, min(i, j)));
				
	printf("%d\n", Res);
}
```