#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;

LL ans = 0x3f3f3f3f3f3f3f3f;
LL ca[20005],cb[20005],ba[20005];
string a,b,c;

void solve(string x,string y,string z){
	LL lx = x.length(),ly = y.length(),lz = z.length();
	x = ' ' + x; y = ' ' + y; z = ' ' + z;
	for(LL i = 1;i <= 20000;i ++){ ba[i] = 1; cb[i] = 1; ca[i] = 1; }
	
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= ly;j ++){
			if(i + j > lx) break;
			if(x[i + j] != y[j] && x[i + j] != '?' && y[j] != '?') flg = 0;
		}
		ba[i + 1] = flg;
	}
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= lz;j ++){
			if(i + j > ly) break;
			if(y[i + j] != z[j] && y[i + j] != '?' && z[j] != '?') flg = 0;
		}
		cb[i + 1] = flg;
	}
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= lz;j ++){
			if(i + j > lx) break;
			if(x[i + j] != z[j] && x[i + j] != '?' && z[j] != '?') flg = 0;
		}
		ca[i + 1] = flg;
	}
	
	for(LL i = 1;i <= 6005;i ++){
		for(LL j = 1;j <= 6005;j ++){
			if(ba[i] && cb[j] && ca[i + j - 1]) ans = min(ans,max(lx,max(i + ly - 1LL,i + j + lz - 2LL)));
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin >> a >> b >> c;
	solve(a,b,c);
	solve(a,c,b);
	solve(b,a,c);
	solve(b,c,a);
	solve(c,a,b);
	solve(c,b,a);
	cout << ans << endl;
	return 0;
}
### Prompt

In cpp, your task is to solve 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 <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;

LL ans = 0x3f3f3f3f3f3f3f3f;
LL ca[20005],cb[20005],ba[20005];
string a,b,c;

void solve(string x,string y,string z){
	LL lx = x.length(),ly = y.length(),lz = z.length();
	x = ' ' + x; y = ' ' + y; z = ' ' + z;
	for(LL i = 1;i <= 20000;i ++){ ba[i] = 1; cb[i] = 1; ca[i] = 1; }
	
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= ly;j ++){
			if(i + j > lx) break;
			if(x[i + j] != y[j] && x[i + j] != '?' && y[j] != '?') flg = 0;
		}
		ba[i + 1] = flg;
	}
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= lz;j ++){
			if(i + j > ly) break;
			if(y[i + j] != z[j] && y[i + j] != '?' && z[j] != '?') flg = 0;
		}
		cb[i + 1] = flg;
	}
	for(LL i = 0;i <= 6005;i ++){
		LL flg = 1;
		for(LL j = 1;j <= lz;j ++){
			if(i + j > lx) break;
			if(x[i + j] != z[j] && x[i + j] != '?' && z[j] != '?') flg = 0;
		}
		ca[i + 1] = flg;
	}
	
	for(LL i = 1;i <= 6005;i ++){
		for(LL j = 1;j <= 6005;j ++){
			if(ba[i] && cb[j] && ca[i + j - 1]) ans = min(ans,max(lx,max(i + ly - 1LL,i + j + lz - 2LL)));
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin >> a >> b >> c;
	solve(a,b,c);
	solve(a,c,b);
	solve(b,a,c);
	solve(b,c,a);
	solve(c,a,b);
	solve(c,b,a);
	cout << ans << endl;
	return 0;
}
```