#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void calc(const string& a, const string& b, vector<int>& res) {
    int na = a.size(), nb = b.size();

    res.resize(na + 1, true);
    for (int i = 0; i < na; ++i) {
        for (int j = 0; j < nb; ++j) {
            if (i + j >= na) break;
            if (a[i + j] != b[j] && a[i + j] != '?' && b[j] != '?') {
                res[i] = false;
                break;
            }
        }
    }
}

int solve(const string& a, const string& b, const string& c) {
    int na = a.size(), nb = b.size(), nc = c.size();

    vector<int> dp_ab, dp_bc, dp_ac;
    calc(a, b, dp_ab);
    calc(b, c, dp_bc);
    calc(a, c, dp_ac);

    int ans = na + nb + nc;
    for (int i = 0; i <= na; ++i) {
        if (!dp_ab[min(i, na)]) continue;
        for (int j = 0; j <= max(nb, na - i); ++j) {
            if (!dp_bc[min(j, nb)] || !dp_ac[min(i + j, na)]) continue;
            ans = min(ans, max({na, i + nb, i + j + nc}));
        }
    }
    return ans;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    array<string, 3> vs;
    for (int i = 0; i < 3; ++i) {
        cin >> vs[i];
    }

    vector<int> ids = {0,1,2};
    int ans = 10000;
    do {
        ans = min(ans, solve(vs[ids[0]], vs[ids[1]], vs[ids[2]]));
    } while (next_permutation(ids.begin(), ids.end()));
    cout << ans << "\n";
    return 0;
}
### Prompt

In Cpp, your task is to solve 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;

using ll = long long;

void calc(const string& a, const string& b, vector<int>& res) {
    int na = a.size(), nb = b.size();

    res.resize(na + 1, true);
    for (int i = 0; i < na; ++i) {
        for (int j = 0; j < nb; ++j) {
            if (i + j >= na) break;
            if (a[i + j] != b[j] && a[i + j] != '?' && b[j] != '?') {
                res[i] = false;
                break;
            }
        }
    }
}

int solve(const string& a, const string& b, const string& c) {
    int na = a.size(), nb = b.size(), nc = c.size();

    vector<int> dp_ab, dp_bc, dp_ac;
    calc(a, b, dp_ab);
    calc(b, c, dp_bc);
    calc(a, c, dp_ac);

    int ans = na + nb + nc;
    for (int i = 0; i <= na; ++i) {
        if (!dp_ab[min(i, na)]) continue;
        for (int j = 0; j <= max(nb, na - i); ++j) {
            if (!dp_bc[min(j, nb)] || !dp_ac[min(i + j, na)]) continue;
            ans = min(ans, max({na, i + nb, i + j + nc}));
        }
    }
    return ans;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    array<string, 3> vs;
    for (int i = 0; i < 3; ++i) {
        cin >> vs[i];
    }

    vector<int> ids = {0,1,2};
    int ans = 10000;
    do {
        ans = min(ans, solve(vs[ids[0]], vs[ids[1]], vs[ids[2]]));
    } while (next_permutation(ids.begin(), ids.end()));
    cout << ans << "\n";
    return 0;
}
```