#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = (1 << 30);

string a, b, c;

void input(void) { cin >> a >> b >> c; }

vector<int> merge_ab(20001, 1), merge_bc(20001, 1), merge_ca(20001, 1);

void build(void) {
	auto judge = [](char c1, char c2) {
		return (c1 == '?' || c2 == '?' || c1 == c2);
	};
	for (int i = 0; i < (int)a.size(); ++i)
		for (int j = 0; j < (int)b.size(); ++j)
			merge_ab[i - j + 10000] &= judge(a[i], b[j]);
	for (int i = 0; i < (int)b.size(); ++i)
		for (int j = 0; j < (int)c.size(); ++j)
			merge_bc[i - j + 10000] &= judge(b[i], c[j]);
	for (int i = 0; i < (int)c.size(); ++i)
		for (int j = 0; j < (int)a.size(); ++j)
			merge_ca[i - j + 10000] &= judge(c[i], a[j]);
}

int main(void) {
	input(); build();
	int res = INF;
	for (int b_st = -5000; b_st <= 5000; ++b_st) {
		if (!merge_ab[b_st + 10000]) continue;
		for (int c_st = -5000; c_st <= 5000; ++c_st) {
			bool ok = merge_bc[c_st - b_st + 10000] && merge_ca[-c_st + 10000];
			if (!ok) continue;
			int r = max({ (int)a.size(), (int)b.size() + b_st, (int)c.size() + c_st });
			int l = min({ 0, b_st, c_st });
			res = min(res, r - l);
		}
	}
	cout << res << endl;
	return 0;
}

### 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
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = (1 << 30);

string a, b, c;

void input(void) { cin >> a >> b >> c; }

vector<int> merge_ab(20001, 1), merge_bc(20001, 1), merge_ca(20001, 1);

void build(void) {
	auto judge = [](char c1, char c2) {
		return (c1 == '?' || c2 == '?' || c1 == c2);
	};
	for (int i = 0; i < (int)a.size(); ++i)
		for (int j = 0; j < (int)b.size(); ++j)
			merge_ab[i - j + 10000] &= judge(a[i], b[j]);
	for (int i = 0; i < (int)b.size(); ++i)
		for (int j = 0; j < (int)c.size(); ++j)
			merge_bc[i - j + 10000] &= judge(b[i], c[j]);
	for (int i = 0; i < (int)c.size(); ++i)
		for (int j = 0; j < (int)a.size(); ++j)
			merge_ca[i - j + 10000] &= judge(c[i], a[j]);
}

int main(void) {
	input(); build();
	int res = INF;
	for (int b_st = -5000; b_st <= 5000; ++b_st) {
		if (!merge_ab[b_st + 10000]) continue;
		for (int c_st = -5000; c_st <= 5000; ++c_st) {
			bool ok = merge_bc[c_st - b_st + 10000] && merge_ca[-c_st + 10000];
			if (!ok) continue;
			int r = max({ (int)a.size(), (int)b.size() + b_st, (int)c.size() + c_st });
			int l = min({ 0, b_st, c_st });
			res = min(res, r - l);
		}
	}
	cout << res << endl;
	return 0;
}

```