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

bool match(char c, char d) {
  if (c == '?' or d == '?') {
    return true;
  }
  return c == d;
}

vector<bool> f(const string& s, const string& t) {
  int n = s.size();
  vector<bool> res(n + 1, true);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < (int)t.size(); ++j) {
      if (i + j < n and not match(s[i + j], t[j])) {
        res[i] = false;
        break;
      }
    }
  }
  return res;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vector<string> s(3);
  for (auto&& e : s) {
    cin >> e;
  }
  sort(begin(s), end(s));
  int res = 1e9;
  do {
    auto b01 = f(s[0], s[1]);
    auto b02 = f(s[0], s[2]);
    auto b12 = f(s[1], s[2]);
    for (int i = 0; i <= (int)s[0].size(); ++i) {
      for (int j = i; j <= max((int)s[0].size(), i + (int)s[1].size()); ++j) {
        if (b01[i] and (j > (int)s[0].size() or b02[j]) and (j - i > (int)s[1].size() or b12[j - i])) {
          res = min(res, max({(int)s[0].size(), i + (int)s[1].size(), j + (int)s[2].size()}));
        }
      }
    }
  } while (next_permutation(begin(s), end(s)));
  cout << res << '\n';
}

### 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 <bits/stdc++.h>
using namespace std;

bool match(char c, char d) {
  if (c == '?' or d == '?') {
    return true;
  }
  return c == d;
}

vector<bool> f(const string& s, const string& t) {
  int n = s.size();
  vector<bool> res(n + 1, true);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < (int)t.size(); ++j) {
      if (i + j < n and not match(s[i + j], t[j])) {
        res[i] = false;
        break;
      }
    }
  }
  return res;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vector<string> s(3);
  for (auto&& e : s) {
    cin >> e;
  }
  sort(begin(s), end(s));
  int res = 1e9;
  do {
    auto b01 = f(s[0], s[1]);
    auto b02 = f(s[0], s[2]);
    auto b12 = f(s[1], s[2]);
    for (int i = 0; i <= (int)s[0].size(); ++i) {
      for (int j = i; j <= max((int)s[0].size(), i + (int)s[1].size()); ++j) {
        if (b01[i] and (j > (int)s[0].size() or b02[j]) and (j - i > (int)s[1].size() or b12[j - i])) {
          res = min(res, max({(int)s[0].size(), i + (int)s[1].size(), j + (int)s[2].size()}));
        }
      }
    }
  } while (next_permutation(begin(s), end(s)));
  cout << res << '\n';
}

```