#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	std::string s[3];
	for (auto &i : s) std::cin >> i;
	std::sort(s, s + 3);
	int res = 1000000000;
	do {
		int n[3];
		for (int i = 0; i < 3; i++) n[i] = s[i].size();
		std::vector<int> slide[3];
		int head = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < i; j++) {
				int max = (i == 2 && j == 0) ? 4000 : 2000;
				for (int k = 0; k <= max; k++) {
					bool ok = true;
					for (int l = k; l < n[j]; l++) {
						if (l - k < n[i] && s[i][l - k] != '?' && s[j][l] != '?' && s[i][l - k] != s[j][l]) ok = false;
					}
					if (ok) slide[head].push_back(k);
				}
				head++;
			}
		}
		std::vector<bool> ok(4001);
		for (auto i : slide[1]) ok[i] = true;
		for (auto i : slide[0]) {
			for (auto j : slide[2]) {
				if (ok[i + j]) res = std::min(res, std::max({n[0], n[1] + i, n[2] + i + j}));
			}
		}
	} while (std::next_permutation(s, s + 3));
	printf("%d\n", res);
	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>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	std::string s[3];
	for (auto &i : s) std::cin >> i;
	std::sort(s, s + 3);
	int res = 1000000000;
	do {
		int n[3];
		for (int i = 0; i < 3; i++) n[i] = s[i].size();
		std::vector<int> slide[3];
		int head = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < i; j++) {
				int max = (i == 2 && j == 0) ? 4000 : 2000;
				for (int k = 0; k <= max; k++) {
					bool ok = true;
					for (int l = k; l < n[j]; l++) {
						if (l - k < n[i] && s[i][l - k] != '?' && s[j][l] != '?' && s[i][l - k] != s[j][l]) ok = false;
					}
					if (ok) slide[head].push_back(k);
				}
				head++;
			}
		}
		std::vector<bool> ok(4001);
		for (auto i : slide[1]) ok[i] = true;
		for (auto i : slide[0]) {
			for (auto j : slide[2]) {
				if (ok[i + j]) res = std::min(res, std::max({n[0], n[1] + i, n[2] + i + j}));
			}
		}
	} while (std::next_permutation(s, s + 3));
	printf("%d\n", res);
	return 0;
}



```