#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s[3];
	for (auto& ss: s) {
		cin >> ss;
	}
	bool can[3][3][2001] = {};
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int shift = 0; shift <= 2000; ++shift) {
				can[i][j][shift] = true;
				for (int k = 0; k < s[j].size() && k + shift < s[i].size(); ++k) {
					if (s[i][k + shift] != '?' && s[j][k] != '?' && s[i][k + shift] != s[j][k]) {
						can[i][j][shift] = false;
						break;
					}
				}
			}
		}
	}
	int p[] = {0, 1, 2};
	auto ans = s[0].size() + s[1].size() + s[2].size();
	do {
		for (int sh1 = 0; sh1 <= 2000; ++sh1) {
			for (int sh2 = 0; sh2 <= 2000; ++sh2) {
				int sh3 = sh1 + sh2;
				if (can[p[0]][p[1]][sh1] && can[p[1]][p[2]][sh2] && (sh3 > 2000 || can[p[0]][p[2]][sh3])) {
					ans = min(ans, max(s[p[0]].size(), max(sh1 + s[p[1]].size(), sh3 + s[p[2]].size())));
				}
			}
		}
	} while (next_permutation(p, p + 3));
	cout << ans << endl;
}
### Prompt

Your task is to create 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>
#define endl '\n'

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s[3];
	for (auto& ss: s) {
		cin >> ss;
	}
	bool can[3][3][2001] = {};
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int shift = 0; shift <= 2000; ++shift) {
				can[i][j][shift] = true;
				for (int k = 0; k < s[j].size() && k + shift < s[i].size(); ++k) {
					if (s[i][k + shift] != '?' && s[j][k] != '?' && s[i][k + shift] != s[j][k]) {
						can[i][j][shift] = false;
						break;
					}
				}
			}
		}
	}
	int p[] = {0, 1, 2};
	auto ans = s[0].size() + s[1].size() + s[2].size();
	do {
		for (int sh1 = 0; sh1 <= 2000; ++sh1) {
			for (int sh2 = 0; sh2 <= 2000; ++sh2) {
				int sh3 = sh1 + sh2;
				if (can[p[0]][p[1]][sh1] && can[p[1]][p[2]][sh2] && (sh3 > 2000 || can[p[0]][p[2]][sh3])) {
					ans = min(ans, max(s[p[0]].size(), max(sh1 + s[p[1]].size(), sh3 + s[p[2]].size())));
				}
			}
		}
	} while (next_permutation(p, p + 3));
	cout << ans << endl;
}
```