#include<bits/stdc++.h>

int main(){
    using namespace std;
    string a, b, c;
    cin >> a >> b >> c;
    long L = a.size(), M = b.size(), N = c.size();
    const auto& dif = [](const string& a, long i, const string& b, long j) -> char {
        if(i < 0 || i >= static_cast<long>(a.size()) || a[i] == '?')return false;
        if(j < 0 || j >= static_cast<long>(b.size()) || b[j] == '?')return false;
        return a[i] != b[j];
    };
    vector<long> ab, bc;
    vector<unsigned long> ac(L + N + 2 * M + 1UL);
    for(long i{-M - N}; i <= L + N; ++i)if([&]{ for(unsigned long j{0}; j < M; ++j)if(dif(a, i + j, b, j))return false;return true; }())ab.push_back(i);
    for(long i{-N - L}; i <= M + L; ++i)if([&]{ for(unsigned long j{0}; j < N; ++j)if(dif(b, i + j, c, j))return false;return true; }())bc.push_back(i);
    for(long i{-N - M}; i <= L + M; ++i)ac[i + N + M] = [&]{ for(unsigned long j{0}; j < N; ++j)if(dif(a, i + j, c, j))return 0UL;return 1UL; }();
    unsigned long ans{numeric_limits<unsigned long>::max()};
    for(const auto& i : ab)for(const auto& j : bc)if(i + j + N + M >= 0 && i + j <= L + M && ac[i + j + N + M])ans = min(ans, 0UL + max({L, i + M, i + j + N}) - min({0L, i, i + j}));
    cout << ans << endl;
    return 0;
}
### Prompt

Please provide a CPP coded solution 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>

int main(){
    using namespace std;
    string a, b, c;
    cin >> a >> b >> c;
    long L = a.size(), M = b.size(), N = c.size();
    const auto& dif = [](const string& a, long i, const string& b, long j) -> char {
        if(i < 0 || i >= static_cast<long>(a.size()) || a[i] == '?')return false;
        if(j < 0 || j >= static_cast<long>(b.size()) || b[j] == '?')return false;
        return a[i] != b[j];
    };
    vector<long> ab, bc;
    vector<unsigned long> ac(L + N + 2 * M + 1UL);
    for(long i{-M - N}; i <= L + N; ++i)if([&]{ for(unsigned long j{0}; j < M; ++j)if(dif(a, i + j, b, j))return false;return true; }())ab.push_back(i);
    for(long i{-N - L}; i <= M + L; ++i)if([&]{ for(unsigned long j{0}; j < N; ++j)if(dif(b, i + j, c, j))return false;return true; }())bc.push_back(i);
    for(long i{-N - M}; i <= L + M; ++i)ac[i + N + M] = [&]{ for(unsigned long j{0}; j < N; ++j)if(dif(a, i + j, c, j))return 0UL;return 1UL; }();
    unsigned long ans{numeric_limits<unsigned long>::max()};
    for(const auto& i : ab)for(const auto& j : bc)if(i + j + N + M >= 0 && i + j <= L + M && ac[i + j + N + M])ans = min(ans, 0UL + max({L, i + M, i + j + N}) - min({0L, i, i + j}));
    cout << ans << endl;
    return 0;
}
```