#include<bits/stdc++.h>

using namespace std;

int ans = -1;

inline void solve(string a, string b, string c) {
    for (int i = 0; i <= (int)a.size(); ++i) {
        int ok = 1;
        for (int j = i; j < min((int)a.size(), i + (int)b.size()) && ok; ++j) {
            if (a[j] != b[j - i] && a[j] != '?' && b[j - i] != '?') ok = 0;
        }
        if (ok == 0) continue;
        int N = max((int)a.size(), i + (int)b.size());
        for (int j = 0; j <= N; ++j) {
            int nxt = max(N, j + (int)c.size());
            if (ans != -1 && nxt >= ans) break;
            ok = 1;
            for (int z = j; z < min(N, j + (int)c.size()) && ok; ++z) {
                if (c[z - j] == '?') continue;
                char f = '?';
                if (z < (int)a.size() && a[z] != '?') f = a[z];
                if (z < i + (int)b.size() && b[z - i] != '?') f = b[z - i];
                if (f == '?') continue;
                if (f != c[z - j]) ok = 0;
            }
            if (ok) {
                ans = nxt;
            }
        }
    }
}

int main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    solve(a, b, c);
    solve(a, c, b);
    solve(b, a, c);
    solve(b, c, a);
    solve(c, a, b);
    solve(c, b, a);
    cout << ans << '\n';
    return 0;
}


### Prompt

Please create a solution in cpp 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;

int ans = -1;

inline void solve(string a, string b, string c) {
    for (int i = 0; i <= (int)a.size(); ++i) {
        int ok = 1;
        for (int j = i; j < min((int)a.size(), i + (int)b.size()) && ok; ++j) {
            if (a[j] != b[j - i] && a[j] != '?' && b[j - i] != '?') ok = 0;
        }
        if (ok == 0) continue;
        int N = max((int)a.size(), i + (int)b.size());
        for (int j = 0; j <= N; ++j) {
            int nxt = max(N, j + (int)c.size());
            if (ans != -1 && nxt >= ans) break;
            ok = 1;
            for (int z = j; z < min(N, j + (int)c.size()) && ok; ++z) {
                if (c[z - j] == '?') continue;
                char f = '?';
                if (z < (int)a.size() && a[z] != '?') f = a[z];
                if (z < i + (int)b.size() && b[z - i] != '?') f = b[z - i];
                if (f == '?') continue;
                if (f != c[z - j]) ok = 0;
            }
            if (ok) {
                ans = nxt;
            }
        }
    }
}

int main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    solve(a, b, c);
    solve(a, c, b);
    solve(b, a, c);
    solve(b, c, a);
    solve(c, a, b);
    solve(c, b, a);
    cout << ans << '\n';
    return 0;
}


```