#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

bool match(char x, char y) {
  return (x == y) || x == '?' || y == '?';
}

vector<bool> diff_k(const string &a, const string &b) {
  vector<bool> res(4040, true);
  rep(k, 4040) {
    rep(i, a.size()) {
      ll j = i - k;
      if (j < 0 || j >= b.size())
        continue;
      if (!match(a[i], b[j]))
        res[k] = false;
    }
  }
  return res;
}

signed main() {
  ll ans = 1000000;
  vector<string> v(3);
  rep(i,3) { cin >> v[i]; }
  sort(begin(v), end(v));
  do {
    auto &a = v[0], &b = v[1], &c = v[2];

    auto d1 = diff_k(a, b); // b を a からk文字ずらしたときに、成り立つかどうか
    auto d2 = diff_k(a, c); // c を a からk文字ずらしたときに、成り立つかどうか
    auto d3 = diff_k(b, c); // c を b からk文字ずらしたときに、成り立つかどうか

    rep(x, 2020)
      rep(y, 2020)
        if (d1[x] && d2[x+y] && d3[y]) {
          ll t = max({(ll)a.size(), (ll)b.size()+x, (ll)c.size()+x+y});
          chmin(ans, t);
        }
  } while(next_permutation(begin(v), end(v)));
  cout << ans << endl;
  return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

bool match(char x, char y) {
  return (x == y) || x == '?' || y == '?';
}

vector<bool> diff_k(const string &a, const string &b) {
  vector<bool> res(4040, true);
  rep(k, 4040) {
    rep(i, a.size()) {
      ll j = i - k;
      if (j < 0 || j >= b.size())
        continue;
      if (!match(a[i], b[j]))
        res[k] = false;
    }
  }
  return res;
}

signed main() {
  ll ans = 1000000;
  vector<string> v(3);
  rep(i,3) { cin >> v[i]; }
  sort(begin(v), end(v));
  do {
    auto &a = v[0], &b = v[1], &c = v[2];

    auto d1 = diff_k(a, b); // b を a からk文字ずらしたときに、成り立つかどうか
    auto d2 = diff_k(a, c); // c を a からk文字ずらしたときに、成り立つかどうか
    auto d3 = diff_k(b, c); // c を b からk文字ずらしたときに、成り立つかどうか

    rep(x, 2020)
      rep(y, 2020)
        if (d1[x] && d2[x+y] && d3[y]) {
          ll t = max({(ll)a.size(), (ll)b.size()+x, (ll)c.size()+x+y});
          chmin(ans, t);
        }
  } while(next_permutation(begin(v), end(v)));
  cout << ans << endl;
  return 0;
}

```