#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
vector<bool> check(string S, string T, int lim) {
	vector<bool> res(2 * lim + 1, true);
	for (int i = -lim; i <= lim; ++i) {
		for (int j = 0; j < S.size(); ++j) {
			int t = j - i;
			if (0 <= t && t < int(T.size()) && S[j] != '?' && T[t] != '?' && S[j] != T[t]) {
				res[i + lim] = false;
				break;
			}
		}
	}
	return res;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	string A, B, C;
	cin >> A >> B >> C;
	int len = A.size() + B.size() + C.size();
	vector<bool> resab = check(A, B, len);
	vector<bool> resbc = check(B, C, len);
	vector<bool> resac = check(A, C, len);
	int ans = (1 << 30);
	for (int i = -len; i <= len; ++i) {
		if (!resab[i + len]) continue;
		for (int j = -len; j <= len; ++j) {
			if (!resbc[j + len]) continue;
			int k = i + j;
			if (-len <= k && k <= len && resac[k + len]) {
				int sa = 0, sb = sa + i, sc = sb + j;
				int pl = min({ sa, sb, sc });
				int pr = max({ sa + int(A.size()), sb + int(B.size()), sc + int(C.size()) });
				ans = min(ans, pr - pl);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
### Prompt

Create a solution in CPP for 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 <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
vector<bool> check(string S, string T, int lim) {
	vector<bool> res(2 * lim + 1, true);
	for (int i = -lim; i <= lim; ++i) {
		for (int j = 0; j < S.size(); ++j) {
			int t = j - i;
			if (0 <= t && t < int(T.size()) && S[j] != '?' && T[t] != '?' && S[j] != T[t]) {
				res[i + lim] = false;
				break;
			}
		}
	}
	return res;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	string A, B, C;
	cin >> A >> B >> C;
	int len = A.size() + B.size() + C.size();
	vector<bool> resab = check(A, B, len);
	vector<bool> resbc = check(B, C, len);
	vector<bool> resac = check(A, C, len);
	int ans = (1 << 30);
	for (int i = -len; i <= len; ++i) {
		if (!resab[i + len]) continue;
		for (int j = -len; j <= len; ++j) {
			if (!resbc[j + len]) continue;
			int k = i + j;
			if (-len <= k && k <= len && resac[k + len]) {
				int sa = 0, sb = sa + i, sc = sb + j;
				int pl = min({ sa, sb, sc });
				int pr = max({ sa + int(A.size()), sb + int(B.size()), sc + int(C.size()) });
				ans = min(ans, pr - pl);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```