#include <bits/stdc++.h>

using namespace std;

string a[3];
const int N = int(1e4 + 10);
bool poss[3][3][N];
int f[3];

bool solve(int i, int j, int k){
	for(int d = k ; d < a[i].length() && (d - k < a[j].length()) ; d++){
		if(a[i][d] != a[j][d - k] && a[i][d] != '?' && a[j][d - k] != '?'){
			return false;
		}
	}

	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> a[0] >> a[1] >> a[2];

	for(int i = 0 ; i < 3 ; i++){
		f[i] = i;

		for(int j = 0 ; j < 3 ; j++){
			if(i == j){
				continue;
			}

			for(int k = 0 ; k <= a[i].length() ; k++){
				poss[i][j][k] = solve(i, j, k);
			}
		}
	}

	int ans = int(1e9);

	do{
		for(int d = 0 ; d <= a[f[0]].length() ; d++){
			if(poss[f[0]][f[1]][d]){
				for(int j = 0 ; j <= max(a[f[1]].length(), a[f[0]].length()) ; j++){
					if(d + j > a[f[0]].length() || poss[f[0]][f[2]][d + j]){
						if(j > a[f[1]].length() || poss[f[1]][f[2]][j]){
							ans = min(ans, max({j + d + int(a[f[2]].length()), 
								d + int(a[f[1]].length()), int(a[f[0]].length())}));
						}
					}
				}
			}
		}
	}while(next_permutation(f, f + 3));

	cout << ans << endl;

	return 0;
}
### Prompt

In CPP, your task is to solve 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>

using namespace std;

string a[3];
const int N = int(1e4 + 10);
bool poss[3][3][N];
int f[3];

bool solve(int i, int j, int k){
	for(int d = k ; d < a[i].length() && (d - k < a[j].length()) ; d++){
		if(a[i][d] != a[j][d - k] && a[i][d] != '?' && a[j][d - k] != '?'){
			return false;
		}
	}

	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> a[0] >> a[1] >> a[2];

	for(int i = 0 ; i < 3 ; i++){
		f[i] = i;

		for(int j = 0 ; j < 3 ; j++){
			if(i == j){
				continue;
			}

			for(int k = 0 ; k <= a[i].length() ; k++){
				poss[i][j][k] = solve(i, j, k);
			}
		}
	}

	int ans = int(1e9);

	do{
		for(int d = 0 ; d <= a[f[0]].length() ; d++){
			if(poss[f[0]][f[1]][d]){
				for(int j = 0 ; j <= max(a[f[1]].length(), a[f[0]].length()) ; j++){
					if(d + j > a[f[0]].length() || poss[f[0]][f[2]][d + j]){
						if(j > a[f[1]].length() || poss[f[1]][f[2]][j]){
							ans = min(ans, max({j + d + int(a[f[2]].length()), 
								d + int(a[f[1]].length()), int(a[f[0]].length())}));
						}
					}
				}
			}
		}
	}while(next_permutation(f, f + 3));

	cout << ans << endl;

	return 0;
}
```