#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  vs s(3);
  rep(i, 3) cin >> s[i];
  sort(all(s));
  bool ok[3][3][4008];
  rep(i, 3) rep(j, 3) rep(k, 4008) ok[i][j][k] = true;
  rep(i, 3) rep(j, 3) {
    if(i == j) continue;
    int m = s[i].size();
    int n = s[j].size();
    rep(a, m) {
      bool same = true;
      rep(b, min(n, m - a)) {
        char x = s[i][a + b];
        char y = s[j][b];
        if(x != y && x != '?' && y != '?') same = false;
      }
      ok[i][j][a] = same;
    }
  }
  int ans = 1e9;
  vi v = {0, 1, 2};
  do {
    int l = s[v[0]].size();
    int m = s[v[1]].size();
    int n = s[v[2]].size();
    rep(i, l + 1) rep(j, max(m + 1, l - i + 1)) {
      bool ac = ok[v[0]][v[1]][i] && ok[v[1]][v[2]][j] && ok[v[0]][v[2]][i + j];
      int d = max(l, max(i + m, i + j + n));
      if(ac) ans = min(ans, d);
    }
  } while(next_permutation(all(v)));
  cout << ans << endl;
}
### Prompt

Your task is to create a cpp solution 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;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  vs s(3);
  rep(i, 3) cin >> s[i];
  sort(all(s));
  bool ok[3][3][4008];
  rep(i, 3) rep(j, 3) rep(k, 4008) ok[i][j][k] = true;
  rep(i, 3) rep(j, 3) {
    if(i == j) continue;
    int m = s[i].size();
    int n = s[j].size();
    rep(a, m) {
      bool same = true;
      rep(b, min(n, m - a)) {
        char x = s[i][a + b];
        char y = s[j][b];
        if(x != y && x != '?' && y != '?') same = false;
      }
      ok[i][j][a] = same;
    }
  }
  int ans = 1e9;
  vi v = {0, 1, 2};
  do {
    int l = s[v[0]].size();
    int m = s[v[1]].size();
    int n = s[v[2]].size();
    rep(i, l + 1) rep(j, max(m + 1, l - i + 1)) {
      bool ac = ok[v[0]][v[1]][i] && ok[v[1]][v[2]][j] && ok[v[0]][v[2]][i + j];
      int d = max(l, max(i + m, i + j + n));
      if(ac) ans = min(ans, d);
    }
  } while(next_permutation(all(v)));
  cout << ans << endl;
}
```