#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

bool can(string s1, string s2, int pos){
	for(int j = pos; j < pos + s2.size() && j < s1.size(); j++){
		if(s1[j] != '?' && s2[j-pos] != '?' && s1[j] != s2[j-pos]){
			return 0;
		}
	}
	return 1;
}
bool ok[3][3][2020];
string s[3];

int get_it(int a, int b, int c){
	int ans = s[a].size() + s[b].size() + s[c].size();
	for(int pos1 = 0; pos1 <= s[a].size(); pos1++){
		for(int pos2 = 0; pos2 <= s[b].size() || pos1 + pos2 <= s[a].size(); pos2++){
			if(ok[a][b][pos1] && (pos2 >= s[b].size() || ok[b][c][pos2]) && (pos1 + pos2 >= s[a].size() || ok[a][c][pos1 + pos2])){
				ans = min(ans, max({pos1 + pos2 + (int)s[c].size(), pos1 + (int)s[b].size(), (int)s[a].size()}));
			}
		}
	}
	return ans;
}

int main(){
	cin >> s[0] >> s[1] >> s[2];
	rep(i, 3){
		rep(j, 3){
			rep(pos, s[j].size()){
				ok[j][i][pos] = can(s[j], s[i], pos);
			}
			ok[j][i][s[j].size()] = 1;
		}
	}
	cout << min({get_it(0, 1, 2), get_it(0, 2, 1), get_it(1, 0, 2), 
                 get_it(1, 2, 0), get_it(2, 0, 1), get_it(2, 1, 0)}) << endl;
	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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 rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

bool can(string s1, string s2, int pos){
	for(int j = pos; j < pos + s2.size() && j < s1.size(); j++){
		if(s1[j] != '?' && s2[j-pos] != '?' && s1[j] != s2[j-pos]){
			return 0;
		}
	}
	return 1;
}
bool ok[3][3][2020];
string s[3];

int get_it(int a, int b, int c){
	int ans = s[a].size() + s[b].size() + s[c].size();
	for(int pos1 = 0; pos1 <= s[a].size(); pos1++){
		for(int pos2 = 0; pos2 <= s[b].size() || pos1 + pos2 <= s[a].size(); pos2++){
			if(ok[a][b][pos1] && (pos2 >= s[b].size() || ok[b][c][pos2]) && (pos1 + pos2 >= s[a].size() || ok[a][c][pos1 + pos2])){
				ans = min(ans, max({pos1 + pos2 + (int)s[c].size(), pos1 + (int)s[b].size(), (int)s[a].size()}));
			}
		}
	}
	return ans;
}

int main(){
	cin >> s[0] >> s[1] >> s[2];
	rep(i, 3){
		rep(j, 3){
			rep(pos, s[j].size()){
				ok[j][i][pos] = can(s[j], s[i], pos);
			}
			ok[j][i][s[j].size()] = 1;
		}
	}
	cout << min({get_it(0, 1, 2), get_it(0, 2, 1), get_it(1, 0, 2), 
                 get_it(1, 2, 0), get_it(2, 0, 1), get_it(2, 1, 0)}) << endl;
	return 0;
}
```