#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
#define x first
#define y second
#define pii pair<int , int>
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000 + 7;
const ll LINF = INF * (ll)INF;
const int mod = 998244353;
const int MAX = 2000005;
bool eq(char c1 , char c2)
{
	return c1 == '?' || c2 == '?' || c1 == c2;
}
vector<int> f(string &a, string &b)
{
	vector<int> ans(sz(a) + 1);
	for(int i = 0; i < sz(a); i++)
	{
		bool ok = true;
		for(int j = 0; j < sz(b) && i + j < sz(a); j++)
			ok &= eq(b[j] , a[i + j]);
		ans[i] = ok;
	}
	ans[sz(a)] = 1;
	return ans;
}

int solve(string &a, string &b, string &c)
{
	vector<int> ok1 = f(a , b) , ok2 = f(a, c) , ok3 = f(b, c);

	int ans = INF;
	for(int p1 = 0; p1 <= sz(a); p1++)
		for(int p2 = p1; p2 <= max(sz(a) , p1 + sz(b)); p2++)
		{
			if(ok1[p1] && (p2 >= sz(ok2) || ok2[p2]) && (p2 - p1 >= sz(ok3) || ok3[p2 - p1]))
			{
				
				ans = min(ans , max(sz(a) , max(p1 + sz(b) , p2 + sz(c))));
			}
		}
		
	return ans;
}
	
int main()
{
	ios_base::sync_with_stdio(0);

	vector<string> v(3);
	for(auto &x : v)
		cin >> x;

	sort(v.begin() , v.end());
	int ans = INF;
	do {
		ans = min(ans , solve(v[0] , v[1], v[2]));
	}while(next_permutation(v.begin(), v.end()));
	cout << ans;
}

### Prompt

Generate 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>
using namespace std;
typedef __int128 ll;
#define x first
#define y second
#define pii pair<int , int>
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000 + 7;
const ll LINF = INF * (ll)INF;
const int mod = 998244353;
const int MAX = 2000005;
bool eq(char c1 , char c2)
{
	return c1 == '?' || c2 == '?' || c1 == c2;
}
vector<int> f(string &a, string &b)
{
	vector<int> ans(sz(a) + 1);
	for(int i = 0; i < sz(a); i++)
	{
		bool ok = true;
		for(int j = 0; j < sz(b) && i + j < sz(a); j++)
			ok &= eq(b[j] , a[i + j]);
		ans[i] = ok;
	}
	ans[sz(a)] = 1;
	return ans;
}

int solve(string &a, string &b, string &c)
{
	vector<int> ok1 = f(a , b) , ok2 = f(a, c) , ok3 = f(b, c);

	int ans = INF;
	for(int p1 = 0; p1 <= sz(a); p1++)
		for(int p2 = p1; p2 <= max(sz(a) , p1 + sz(b)); p2++)
		{
			if(ok1[p1] && (p2 >= sz(ok2) || ok2[p2]) && (p2 - p1 >= sz(ok3) || ok3[p2 - p1]))
			{
				
				ans = min(ans , max(sz(a) , max(p1 + sz(b) , p2 + sz(c))));
			}
		}
		
	return ans;
}
	
int main()
{
	ios_base::sync_with_stdio(0);

	vector<string> v(3);
	for(auto &x : v)
		cin >> x;

	sort(v.begin() , v.end());
	int ans = INF;
	do {
		ans = min(ans , solve(v[0] , v[1], v[2]));
	}while(next_permutation(v.begin(), v.end()));
	cout << ans;
}

```