#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n = 3;
	string s[n];
	for(int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	bool ok[n][n][4010];
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			for(int k = 0; k < 4010; ++k) {
				ok[i][j][k] = true;
			} 
		}
	}
	for(int l = 0; l < n; ++l) {
		for(int r = 0; r < n; ++r) {
			for(int i = 0; i < s[l].size(); ++i) {
				for(int j = 0; j < s[r].size() and i + j < s[l].size(); ++j) {
					if(s[l][i + j] != '?' and s[r][j] != '?' and s[l][i + j] != s[r][j]) {
						ok[l][r][i] = false;
					}
				}
			}
		}
	}
	vector<int> v = {0, 1, 2};
	int ans = INF;
	do {
		for(int i = 0; i <= s[v[0]].size(); ++i) {
			for(int j = 0; j <= max<int>(s[v[0]].size() - i, s[v[1]].size()); ++j) {
				if(ok[v[0]][v[1]][i] and ok[v[1]][v[2]][j] and ok[v[0]][v[2]][i + j]) {
					int n0 = s[v[0]].size() - (i + j);
					int n1 = s[v[1]].size() - j;
					int n2 = s[v[2]].size();
					ans = min<int>(ans, i + j + max({n0, n1, n2}));
				}
			}
		}
	} while(next_permutation(v.begin(), v.end()));
	cout << ans << '\n';
	return 0;
}
### 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>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n = 3;
	string s[n];
	for(int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	bool ok[n][n][4010];
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			for(int k = 0; k < 4010; ++k) {
				ok[i][j][k] = true;
			} 
		}
	}
	for(int l = 0; l < n; ++l) {
		for(int r = 0; r < n; ++r) {
			for(int i = 0; i < s[l].size(); ++i) {
				for(int j = 0; j < s[r].size() and i + j < s[l].size(); ++j) {
					if(s[l][i + j] != '?' and s[r][j] != '?' and s[l][i + j] != s[r][j]) {
						ok[l][r][i] = false;
					}
				}
			}
		}
	}
	vector<int> v = {0, 1, 2};
	int ans = INF;
	do {
		for(int i = 0; i <= s[v[0]].size(); ++i) {
			for(int j = 0; j <= max<int>(s[v[0]].size() - i, s[v[1]].size()); ++j) {
				if(ok[v[0]][v[1]][i] and ok[v[1]][v[2]][j] and ok[v[0]][v[2]][i + j]) {
					int n0 = s[v[0]].size() - (i + j);
					int n1 = s[v[1]].size() - j;
					int n2 = s[v[2]].size();
					ans = min<int>(ans, i + j + max({n0, n1, n2}));
				}
			}
		}
	} while(next_permutation(v.begin(), v.end()));
	cout << ans << '\n';
	return 0;
}
```