#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

bool check(const char& a, const char& b) { return (a == '?' || b == '?' || a == b); }

void tapu(vector<bool>& v, const string& a, const string& b) {
	for (int i = 0; i < a.size(); ++i) {
		for (int j = 0; j < b.size(); ++j) {
			if (i + j >= a.size()) { break; }
			if (!check(a[i + j], b[j])) {
				v[i] = false;
				break;
			}
		}
	}
}

int main() {
	const int sz = 4010;
	string s[3];
	for (int i = 0; i < 3; ++i) { cin >> s[i]; }

	int ans = 1e8;
	vector<int> P = { 0, 1, 2 };
	do {
		string a = s[P[0]], b = s[P[1]], c = s[P[2]];
		vector<bool> ab(sz, true), bc(sz, true), ac(sz, true);
		tapu(ab, a, b);
		tapu(bc, b, c);
		tapu(ac, a, c);

		for (int i = 0; i < sz; ++i) {
			for (int j = i; j < sz; ++j) {
				if (ab[i] && bc[j - i] && ac[j]) {
					int n = max({ a.size(), b.size() + i, c.size() + j });
					ans = min(ans, n);
				}
			}
		}
	} while ( next_permutation(P.begin(), P.end()) );

	cout << ans << endl;

	return 0; 
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 Int int64_t

using namespace std;

bool check(const char& a, const char& b) { return (a == '?' || b == '?' || a == b); }

void tapu(vector<bool>& v, const string& a, const string& b) {
	for (int i = 0; i < a.size(); ++i) {
		for (int j = 0; j < b.size(); ++j) {
			if (i + j >= a.size()) { break; }
			if (!check(a[i + j], b[j])) {
				v[i] = false;
				break;
			}
		}
	}
}

int main() {
	const int sz = 4010;
	string s[3];
	for (int i = 0; i < 3; ++i) { cin >> s[i]; }

	int ans = 1e8;
	vector<int> P = { 0, 1, 2 };
	do {
		string a = s[P[0]], b = s[P[1]], c = s[P[2]];
		vector<bool> ab(sz, true), bc(sz, true), ac(sz, true);
		tapu(ab, a, b);
		tapu(bc, b, c);
		tapu(ac, a, c);

		for (int i = 0; i < sz; ++i) {
			for (int j = i; j < sz; ++j) {
				if (ab[i] && bc[j - i] && ac[j]) {
					int n = max({ a.size(), b.size() + i, c.size() + j });
					ans = min(ans, n);
				}
			}
		}
	} while ( next_permutation(P.begin(), P.end()) );

	cout << ans << endl;

	return 0; 
}

```