#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

bool eq(char a, char b) {
  if (a == '?' || b == '?') return true;
  return a == b;
}

vector<int> g(string a, string b) {
  vector<int> res(a.size() + 1);
  for (int i = 0; i <= a.size(); i++) {
    for (int j = 0; i + j < a.size() && j < b.size(); j++) {
      if (eq(a[i + j], b[j])) {
        res[i]++;
      } else break;
    }
  }
  return res;
}

int f(string a, string b, string c) {
  int res = INT_MAX;
  auto ab = g(a, b);
  auto ac = g(a, c);
  auto bc = g(b, c);
  const int A = a.size();
  const int B = b.size();
  const int C = c.size();
  for (int i = 0; i <= A; i++) {
    for (int j = 0; i + j <= A || j <= B; j++) {
      bool ok = true;
      ok &= min(A - i, B) == ab[i];
      ok &= j >= B || min(B - j, C) == bc[j];
      ok &= i + j >= A || min(C, A - (i + j)) == ac[i + j];
      if (ok) {
        res = min(res, max({A, i + B, i + j + C}));
      }
    }
  }
  return res;
}

int main() {
  string a, b, c; cin >> a >> b >> c;
  int ans = INT_MAX;
  ans = min(ans, f(a, b, c));
  ans = min(ans, f(a, c, b));
  ans = min(ans, f(b, a, c));
  ans = min(ans, f(b, c, a));
  ans = min(ans, f(c, a, b));
  ans = min(ans, f(c, b, a));
  cout << ans << endl;
}
### Prompt

Develop a solution in cpp 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;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

bool eq(char a, char b) {
  if (a == '?' || b == '?') return true;
  return a == b;
}

vector<int> g(string a, string b) {
  vector<int> res(a.size() + 1);
  for (int i = 0; i <= a.size(); i++) {
    for (int j = 0; i + j < a.size() && j < b.size(); j++) {
      if (eq(a[i + j], b[j])) {
        res[i]++;
      } else break;
    }
  }
  return res;
}

int f(string a, string b, string c) {
  int res = INT_MAX;
  auto ab = g(a, b);
  auto ac = g(a, c);
  auto bc = g(b, c);
  const int A = a.size();
  const int B = b.size();
  const int C = c.size();
  for (int i = 0; i <= A; i++) {
    for (int j = 0; i + j <= A || j <= B; j++) {
      bool ok = true;
      ok &= min(A - i, B) == ab[i];
      ok &= j >= B || min(B - j, C) == bc[j];
      ok &= i + j >= A || min(C, A - (i + j)) == ac[i + j];
      if (ok) {
        res = min(res, max({A, i + B, i + j + C}));
      }
    }
  }
  return res;
}

int main() {
  string a, b, c; cin >> a >> b >> c;
  int ans = INT_MAX;
  ans = min(ans, f(a, b, c));
  ans = min(ans, f(a, c, b));
  ans = min(ans, f(b, a, c));
  ans = min(ans, f(b, c, a));
  ans = min(ans, f(c, a, b));
  ans = min(ans, f(c, b, a));
  cout << ans << endl;
}
```