#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
const int M = 1e4 + 10;
const int D = 4e3;
char a[N], b[N], c[N];
bool ab[M], ac[M], bc[M];//若true则不满足 
int lena, lenb, lenc;
bool check(int x, int y) {
	return (x == '?' || y == '?' || x == y);
}
int main() {
	scanf("%s%s%s", a, b, c);
	lena = strlen(a);
	lenb = strlen(b);
	lenc = strlen(c);
	for (int i = 0; i < lena; i++) {
		for (int j = 0; j < lenb; j++) {
			if (!check(a[i], b[j])) {
				ab[i - j + D] = 1;
			}
		}
	}
	for (int i = 0; i < lena; i++) {
		for (int j = 0; j < lenc; j++) {
			if (!check(a[i], c[j])) {
				ac[i - j + D] = 1;
			}
		}
	}
	for (int i = 0; i < lenb; i++) {
		for (int j = 0; j < lenc; j++) {
			if (!check(b[i], c[j])) {
				bc[i - j + D] = 1;
			}
		}
	}
	int ans = 0x7f7f7f7f;
	for (int i = -D; i <= D; i++) {
		for (int j = -D; j <= D; j++) {
			if (!ab[i + D] && !ac[j + D] && !bc[j - i + D]) {
				int l = min(0, min(i, j));
				int r = max(lena, max(lenb + i, lenc + j));
				ans = min(ans, r - l); 
			}
		}
	}
	printf("%d", ans);
	return 0;
} 
### Prompt

Please formulate 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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
const int M = 1e4 + 10;
const int D = 4e3;
char a[N], b[N], c[N];
bool ab[M], ac[M], bc[M];//若true则不满足 
int lena, lenb, lenc;
bool check(int x, int y) {
	return (x == '?' || y == '?' || x == y);
}
int main() {
	scanf("%s%s%s", a, b, c);
	lena = strlen(a);
	lenb = strlen(b);
	lenc = strlen(c);
	for (int i = 0; i < lena; i++) {
		for (int j = 0; j < lenb; j++) {
			if (!check(a[i], b[j])) {
				ab[i - j + D] = 1;
			}
		}
	}
	for (int i = 0; i < lena; i++) {
		for (int j = 0; j < lenc; j++) {
			if (!check(a[i], c[j])) {
				ac[i - j + D] = 1;
			}
		}
	}
	for (int i = 0; i < lenb; i++) {
		for (int j = 0; j < lenc; j++) {
			if (!check(b[i], c[j])) {
				bc[i - j + D] = 1;
			}
		}
	}
	int ans = 0x7f7f7f7f;
	for (int i = -D; i <= D; i++) {
		for (int j = -D; j <= D; j++) {
			if (!ab[i + D] && !ac[j + D] && !bc[j - i + D]) {
				int l = min(0, min(i, j));
				int r = max(lena, max(lenb + i, lenc + j));
				ans = min(ans, r - l); 
			}
		}
	}
	printf("%d", ans);
	return 0;
} 
```