#include <bits/stdc++.h>

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

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

constexpr int MAX = 4000;

vector<int> fill_table(const string& a, const string& b, int M) {
    vector<int> res;
    debug(a);
    debug(b);
    int len_a = a.size(), len_b = b.size();
    for (int i = -M; i <= M; ++i) {
        bool ok = true;
        for (int j = max(0, i); j < min(len_a, i + len_b); ++j) {
            if (!match(a[j], b[j - i])) {ok = false; break;}
        }
        res.push_back(ok);
        if (ok) {debug(i);};
    }
    return res;
}

int main() {
    string a, b, c;
    cin >> a >> b >> c;

    vector<int> ab = fill_table(a, b, MAX);
    int ab_begin = -b.size();
    vector<int> ac = fill_table(a, c, MAX);
    int ac_begin = -c.size();
    vector<int> bc = fill_table(b, c, 4 * MAX);
    int bc_begin = -c.size();

    int res = 1e8;
    int len_a = a.size(), len_b = b.size(), len_c = c.size();
    for (int i = -MAX; i <= MAX; ++i) {
        for (int j = -MAX; j <= MAX; ++j) {
            if (ab[i + MAX] && ac[j + MAX] && bc[j - i + 4 * MAX]) {
                res = min<int>(res, max<int>({len_a, len_b + i, len_c + j}) - min<int>({0, i, j}));
                
            }
        }
    }
    cout << res << endl;
}
### Prompt

Develop a solution in cpp 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>

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

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

constexpr int MAX = 4000;

vector<int> fill_table(const string& a, const string& b, int M) {
    vector<int> res;
    debug(a);
    debug(b);
    int len_a = a.size(), len_b = b.size();
    for (int i = -M; i <= M; ++i) {
        bool ok = true;
        for (int j = max(0, i); j < min(len_a, i + len_b); ++j) {
            if (!match(a[j], b[j - i])) {ok = false; break;}
        }
        res.push_back(ok);
        if (ok) {debug(i);};
    }
    return res;
}

int main() {
    string a, b, c;
    cin >> a >> b >> c;

    vector<int> ab = fill_table(a, b, MAX);
    int ab_begin = -b.size();
    vector<int> ac = fill_table(a, c, MAX);
    int ac_begin = -c.size();
    vector<int> bc = fill_table(b, c, 4 * MAX);
    int bc_begin = -c.size();

    int res = 1e8;
    int len_a = a.size(), len_b = b.size(), len_c = c.size();
    for (int i = -MAX; i <= MAX; ++i) {
        for (int j = -MAX; j <= MAX; ++j) {
            if (ab[i + MAX] && ac[j + MAX] && bc[j - i + 4 * MAX]) {
                res = min<int>(res, max<int>({len_a, len_b + i, len_c + j}) - min<int>({0, i, j}));
                
            }
        }
    }
    cout << res << endl;
}
```