#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

vector<bool> f(string &a, string &b) {
    int la = a.size(), lb = b.size();
    vector<bool> ret(la+1, true);
    for (int i = 0; i < la; i++) {
        for (int j = i, k = 0; j < la && k < lb; j++, k++) {
            if (a[j] != '?' && b[k] != '?' && a[j] != b[k]) {
                ret[i] = false;
                break;
            }
        }
    }
    return ret;
}

int calc(string &a, string &b, string &c) {
    vector<bool> ab = f(a, b), bc = f(b, c), ac = f(a, c);
    int la = a.size(), lb = b.size(), lc = c.size(), ans = la+lb+lc;
    for (int i = 0; i <= la; i++) {
        for (int j = 0; j <= max(la, lb); j++) {
            if (ab[i] && (j >= lb || bc[j]) && (i + j >= la || ac[i+j])) {
                ans = min(ans, max({la, i + lb, i + j + lc}));
            }
        }
    }
    return ans;
}


int main() {
    string a, b, c; cin >> a >> b >> c;
    cout << min({calc(a, b, c), calc(a, c, b), calc(b, a, c), calc(b, c, a),
                calc(c, a, b), calc(c, b, a)}) << endl;
}

### Prompt

Please create a solution in cpp 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 <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

vector<bool> f(string &a, string &b) {
    int la = a.size(), lb = b.size();
    vector<bool> ret(la+1, true);
    for (int i = 0; i < la; i++) {
        for (int j = i, k = 0; j < la && k < lb; j++, k++) {
            if (a[j] != '?' && b[k] != '?' && a[j] != b[k]) {
                ret[i] = false;
                break;
            }
        }
    }
    return ret;
}

int calc(string &a, string &b, string &c) {
    vector<bool> ab = f(a, b), bc = f(b, c), ac = f(a, c);
    int la = a.size(), lb = b.size(), lc = c.size(), ans = la+lb+lc;
    for (int i = 0; i <= la; i++) {
        for (int j = 0; j <= max(la, lb); j++) {
            if (ab[i] && (j >= lb || bc[j]) && (i + j >= la || ac[i+j])) {
                ans = min(ans, max({la, i + lb, i + j + lc}));
            }
        }
    }
    return ans;
}


int main() {
    string a, b, c; cin >> a >> b >> c;
    cout << min({calc(a, b, c), calc(a, c, b), calc(b, a, c), calc(b, c, a),
                calc(c, a, b), calc(c, b, a)}) << endl;
}

```