#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 10;
string s[4];
bool no[4][maxn];
bool judge(char a, char b) {
	return !(a == b || a == '?' || b == '?');
}
int main() {
	int ans = 0;
	for (int i = 1; i <= 3; i++) {
		cin >> s[i];
		ans += s[i].size();
	}
	for (int p = 0; p < 6; p++) {
		// for (int i = 1; i <= 3; i++) {
		// 	cout << s[i] << '\n';
		// }
		memset(no, 0, sizeof(no));
		for (int i = 0; i < (int)s[2].size(); i++) {
			for (int j = i; j < (int)s[1].size(); j++) {
				no[1][j - i] |= judge(s[2][i], s[1][j]);
			}
		}
		for (int i = 0; i < (int)s[3].size(); i++) {
			for (int j = i; j < (int)s[2].size(); j++) {
				no[2][j - i] |= judge(s[3][i], s[2][j]);
			}
		}
		for (int i = 0; i < (int)s[3].size(); i++) {
			for (int j = i; j < (int)s[1].size(); j++) {
				no[3][j - i] |= judge(s[3][i], s[1][j]);
			}
		}
		// for (int i = 1; i <= 3; i++) {
		// 	for (int j = 0; j < 7; j++) {
		// 		cout << no[i][j] << ' ';
		// 	} cout << '\n';
		// }
		for (int i = 0; i <= 2000; i++) {
			for (int j = 0; j <= 2000; j++) {
				if ((!no[1][i]) && (!no[2][j]) && (!no[3][i + j])) {
					int len = max(max((int)s[1].size(), i + (int)s[2].size()), i + j + (int)s[3].size());
					ans = min(ans, len);
				}
			}
		}
		next_permutation(s + 1, s + 1 + 3);
	}
	printf("%d\n", ans);
	getchar(); getchar();
	return 0;
}
### Prompt

Please formulate 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 maxn = 10000 + 10;
string s[4];
bool no[4][maxn];
bool judge(char a, char b) {
	return !(a == b || a == '?' || b == '?');
}
int main() {
	int ans = 0;
	for (int i = 1; i <= 3; i++) {
		cin >> s[i];
		ans += s[i].size();
	}
	for (int p = 0; p < 6; p++) {
		// for (int i = 1; i <= 3; i++) {
		// 	cout << s[i] << '\n';
		// }
		memset(no, 0, sizeof(no));
		for (int i = 0; i < (int)s[2].size(); i++) {
			for (int j = i; j < (int)s[1].size(); j++) {
				no[1][j - i] |= judge(s[2][i], s[1][j]);
			}
		}
		for (int i = 0; i < (int)s[3].size(); i++) {
			for (int j = i; j < (int)s[2].size(); j++) {
				no[2][j - i] |= judge(s[3][i], s[2][j]);
			}
		}
		for (int i = 0; i < (int)s[3].size(); i++) {
			for (int j = i; j < (int)s[1].size(); j++) {
				no[3][j - i] |= judge(s[3][i], s[1][j]);
			}
		}
		// for (int i = 1; i <= 3; i++) {
		// 	for (int j = 0; j < 7; j++) {
		// 		cout << no[i][j] << ' ';
		// 	} cout << '\n';
		// }
		for (int i = 0; i <= 2000; i++) {
			for (int j = 0; j <= 2000; j++) {
				if ((!no[1][i]) && (!no[2][j]) && (!no[3][i + j])) {
					int len = max(max((int)s[1].size(), i + (int)s[2].size()), i + j + (int)s[3].size());
					ans = min(ans, len);
				}
			}
		}
		next_permutation(s + 1, s + 1 + 3);
	}
	printf("%d\n", ans);
	getchar(); getchar();
	return 0;
}
```