#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

bool same(char &a, char &b){
    return a == '?' || b == '?' || a == b;
}

int main() {
    string a, b, c;
    cin>>a>>b>>c;
    ll C;
    A = a.size();
    B = b.size();
    C = c.size();
    vector<bool> ab(1e+5, true), bc(1e+5, true), ca(1e+5, true);
    const int m = 50000;
    rep(i, A) rep(j, B) if(!same(a[i], b[j])) ab[i - j + m] = false;
    rep(i, B) rep(j, C) if(!same(b[i], c[j])) bc[i - j + m] = false;
    rep(i, C) rep(j, A) if(!same(c[i], a[j])) ca[i - j + m] = false;
    ll ans = A + B + C;
    reps(i, -4001, 4001) reps(j, -4001, 4001){
        //a:0, b:+i, c:+jなので
        if(ab[i + m] && bc[j - i + m] && ca[m - j]){
            ans = min(ans, max({A, B + i, C + j}) - min({0, i, j}));
        }
    }
    cout<<ans<<endl;
}
### Prompt

Create a solution in cpp for 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>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

bool same(char &a, char &b){
    return a == '?' || b == '?' || a == b;
}

int main() {
    string a, b, c;
    cin>>a>>b>>c;
    ll C;
    A = a.size();
    B = b.size();
    C = c.size();
    vector<bool> ab(1e+5, true), bc(1e+5, true), ca(1e+5, true);
    const int m = 50000;
    rep(i, A) rep(j, B) if(!same(a[i], b[j])) ab[i - j + m] = false;
    rep(i, B) rep(j, C) if(!same(b[i], c[j])) bc[i - j + m] = false;
    rep(i, C) rep(j, A) if(!same(c[i], a[j])) ca[i - j + m] = false;
    ll ans = A + B + C;
    reps(i, -4001, 4001) reps(j, -4001, 4001){
        //a:0, b:+i, c:+jなので
        if(ab[i + m] && bc[j - i + m] && ca[m - j]){
            ans = min(ans, max({A, B + i, C + j}) - min({0, i, j}));
        }
    }
    cout<<ans<<endl;
}
```