#include <bits/stdc++.h>
using namespace std;

int ok1[2010], ok2[2010], ok3[2010];

bool check(string &a, int p1, string &b, int p2) {
    while (p1 < a.size() && p2 < b.size()) {
        if (a[p1] != b[p2] && a[p1] != '?' && b[p2] != '?') return 0;
        p1++, p2++;
    }
    return 1;
}

int solve(string a, string b, string c) {
    for (int i = 0; i <= a.size(); i++) {
        ok1[i] = check(a, i, b, 0);
    }
    for (int i = 0; i <= b.size(); i++) {
        ok2[i] = check(b, i, c, 0);
    }
    for (int i = 0; i <= a.size(); i++) {
        ok3[i] = check(a, i, c, 0);
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= a.size(); i++) {
        for (int j = 0; j <= b.size() || i + j <= a.size(); j++) {
            if (ok1[i] && (j > b.size() || ok2[j]) && (i + j > a.size() || ok3[i + j])) {
                ans = min(ans, (int)max(a.size(), max(i + b.size(), i + j + c.size())));
            }
        }
    }
    return ans;
}

int main () {
    string s[3];
    cin >> s[0] >> s[1] >> s[2];
    sort(s, s + 3);
    int ans = 0x3f3f3f3f;
    do {
        ans = min(ans, solve(s[0], s[1], s[2]));
    } while (next_permutation(s, s + 3));
    cout << ans << endl;
    return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 ok1[2010], ok2[2010], ok3[2010];

bool check(string &a, int p1, string &b, int p2) {
    while (p1 < a.size() && p2 < b.size()) {
        if (a[p1] != b[p2] && a[p1] != '?' && b[p2] != '?') return 0;
        p1++, p2++;
    }
    return 1;
}

int solve(string a, string b, string c) {
    for (int i = 0; i <= a.size(); i++) {
        ok1[i] = check(a, i, b, 0);
    }
    for (int i = 0; i <= b.size(); i++) {
        ok2[i] = check(b, i, c, 0);
    }
    for (int i = 0; i <= a.size(); i++) {
        ok3[i] = check(a, i, c, 0);
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= a.size(); i++) {
        for (int j = 0; j <= b.size() || i + j <= a.size(); j++) {
            if (ok1[i] && (j > b.size() || ok2[j]) && (i + j > a.size() || ok3[i + j])) {
                ans = min(ans, (int)max(a.size(), max(i + b.size(), i + j + c.size())));
            }
        }
    }
    return ans;
}

int main () {
    string s[3];
    cin >> s[0] >> s[1] >> s[2];
    sort(s, s + 3);
    int ans = 0x3f3f3f3f;
    do {
        ans = min(ans, solve(s[0], s[1], s[2]));
    } while (next_permutation(s, s + 3));
    cout << ans << endl;
    return 0;
}
```