#include <bits/stdc++.h>

using namespace std;


#ifdef CLION

ifstream ifs("/home/kyuridenamida/CLionProjects/untitled4/input.txt");
#define cin ifs
#define scanf DONT_USE_SCANF
#endif

typedef long long ll;

int AB = 0;
int AC = 1;
int BC = 2;
bool dp[3][8001];

void build(string a, string b, int dpk) {
    for (int i = -4000; i <= 4000; i++) {
        bool ok = true;
        for (int j = 0; j < b.size(); j++) {
            if (i + j < 0 || i + j >= a.size() || (b[j] == '?' || a[i + j] == '?') || b[j] == a[i + j]) {

            } else {
                ok = false;
            }
        }
        dp[dpk][i + 4000] = ok;
    }
}

int main() {

    string a;
    string b;
    string c;
    cin >> a >> b >> c;
    build(a, b, AB);
    build(a, c, AC);
    build(b, c, BC);

    int ll = a.size() + b.size() + c.size();
    for (int i = -4000; i <= 4000; i++) {
        for (int j = -4000; j <= 4000; j++) {
            if (abs(i - j) <= 4000 && dp[AB][i + 4000] && dp[AC][j + 4000] && dp[BC][j - i + 4000]) {
                int s = max<int>({(int) a.size(), i + (int) b.size(), j + (int) c.size()}) -
                        min<int>({0, i, j});
                ll = min(ll, s);
            }
        }
    }
    cout << ll << endl;
}


### 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>

using namespace std;


#ifdef CLION

ifstream ifs("/home/kyuridenamida/CLionProjects/untitled4/input.txt");
#define cin ifs
#define scanf DONT_USE_SCANF
#endif

typedef long long ll;

int AB = 0;
int AC = 1;
int BC = 2;
bool dp[3][8001];

void build(string a, string b, int dpk) {
    for (int i = -4000; i <= 4000; i++) {
        bool ok = true;
        for (int j = 0; j < b.size(); j++) {
            if (i + j < 0 || i + j >= a.size() || (b[j] == '?' || a[i + j] == '?') || b[j] == a[i + j]) {

            } else {
                ok = false;
            }
        }
        dp[dpk][i + 4000] = ok;
    }
}

int main() {

    string a;
    string b;
    string c;
    cin >> a >> b >> c;
    build(a, b, AB);
    build(a, c, AC);
    build(b, c, BC);

    int ll = a.size() + b.size() + c.size();
    for (int i = -4000; i <= 4000; i++) {
        for (int j = -4000; j <= 4000; j++) {
            if (abs(i - j) <= 4000 && dp[AB][i + 4000] && dp[AC][j + 4000] && dp[BC][j - i + 4000]) {
                int s = max<int>({(int) a.size(), i + (int) b.size(), j + (int) c.size()}) -
                        min<int>({0, i, j});
                ll = min(ll, s);
            }
        }
    }
    cout << ll << endl;
}


```