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

constexpr int M = 2010;

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

int main() {
    string a, b, c; cin >> a >> b >> c;
    int A = a.length();
    int B = b.length();
    int C = c.length();
    vector<bool> ab(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + B; j++) {
            if (0 <= j && j < A) {
                ab[10000 + i] = ab[10000 + i] && match(a[j], b[j-i]);
            }
        }
    }
    vector<bool> ac(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + C; j++) {
            if (0 <= j && j < A) {
                ac[10000 + i] = ac[10000 + i] && match(a[j], c[j-i]);
            }
        }
    }
    vector<bool> bc(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + C; j++) {
            if (0 <= j && j < B) {
                bc[10000 + i] = bc[10000 + i] && match(b[j], c[j-i]);
            }
        }
    }
    int ans = 1000000;
    for (int i = -M * 2; i <= M * 2; i++) {
        for (int j = -M * 2; j <= M * 2; j++) {
            if (ab[10000 + i] && ac[10000 + j] && bc[10000 - i + j]) {
                ans = min(ans, (max({A, i + B, j + C}) - min({0, i, j})));
            }
        }
    }
    cout << ans << endl;
}

### Prompt

Generate a Cpp solution 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;
typedef long long ll;

constexpr int M = 2010;

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

int main() {
    string a, b, c; cin >> a >> b >> c;
    int A = a.length();
    int B = b.length();
    int C = c.length();
    vector<bool> ab(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + B; j++) {
            if (0 <= j && j < A) {
                ab[10000 + i] = ab[10000 + i] && match(a[j], b[j-i]);
            }
        }
    }
    vector<bool> ac(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + C; j++) {
            if (0 <= j && j < A) {
                ac[10000 + i] = ac[10000 + i] && match(a[j], c[j-i]);
            }
        }
    }
    vector<bool> bc(20000, true);
    for (int i = -M; i <= M; i++) {
        for (int j = i; j < i + C; j++) {
            if (0 <= j && j < B) {
                bc[10000 + i] = bc[10000 + i] && match(b[j], c[j-i]);
            }
        }
    }
    int ans = 1000000;
    for (int i = -M * 2; i <= M * 2; i++) {
        for (int j = -M * 2; j <= M * 2; j++) {
            if (ab[10000 + i] && ac[10000 + j] && bc[10000 - i + j]) {
                ans = min(ans, (max({A, i + B, j + C}) - min({0, i, j})));
            }
        }
    }
    cout << ans << endl;
}

```