// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 10055;

string s[3];
int can[3][3][N];

void calc(int i, int j) {
  string& a = s[i];
  string& b = s[j];
  for(int k = 0 ; k < sz(a) ; k++) {
    can[i][j][k] = true;
    for(int l = k ; l < sz(a) && l - k < sz(b) ; l++) {
      can[i][j][k] &= a[l] == '?' || b[l - k] == '?' || a[l] == b[l - k];
    }
  }
  for(int k = sz(a) ; k < N ; k++)
    can[i][j][k] = true;
}

int solve(vector<int>& idx) {
  int a = sz(s[idx[0]]);
  int b = sz(s[idx[1]]);
  int c = sz(s[idx[2]]);
  int ans = 1e9;
  for(int i = 0 ; i <= a ; i++) {
    if(can[idx[0]][idx[1]][i]) {
      for(int j = 0 ; j <= b || i + j <= a ; j++) {
        if(can[idx[1]][idx[2]][j] && can[idx[0]][idx[2]][i + j]) {
          ans = min(ans, max(a, max(b + i, c + i + j)));
        }
      }
    }
  }
  return ans;
}

int main()
{
  for(int i = 0 ; i < 3 ; i++)
    cin >> s[i];
  for(int i = 0 ; i < 3 ; i++)
    for(int j = 0 ; j < 3 ; j++)
      if(i != j)
        calc(i, j);
  vector<int> idx = {0, 1, 2};
  int best = 1e9;
  do {
    best = min(best, solve(idx));
  }while(next_permutation(all(idx)));
  cout << best << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve 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
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 10055;

string s[3];
int can[3][3][N];

void calc(int i, int j) {
  string& a = s[i];
  string& b = s[j];
  for(int k = 0 ; k < sz(a) ; k++) {
    can[i][j][k] = true;
    for(int l = k ; l < sz(a) && l - k < sz(b) ; l++) {
      can[i][j][k] &= a[l] == '?' || b[l - k] == '?' || a[l] == b[l - k];
    }
  }
  for(int k = sz(a) ; k < N ; k++)
    can[i][j][k] = true;
}

int solve(vector<int>& idx) {
  int a = sz(s[idx[0]]);
  int b = sz(s[idx[1]]);
  int c = sz(s[idx[2]]);
  int ans = 1e9;
  for(int i = 0 ; i <= a ; i++) {
    if(can[idx[0]][idx[1]][i]) {
      for(int j = 0 ; j <= b || i + j <= a ; j++) {
        if(can[idx[1]][idx[2]][j] && can[idx[0]][idx[2]][i + j]) {
          ans = min(ans, max(a, max(b + i, c + i + j)));
        }
      }
    }
  }
  return ans;
}

int main()
{
  for(int i = 0 ; i < 3 ; i++)
    cin >> s[i];
  for(int i = 0 ; i < 3 ; i++)
    for(int j = 0 ; j < 3 ; j++)
      if(i != j)
        calc(i, j);
  vector<int> idx = {0, 1, 2};
  int best = 1e9;
  do {
    best = min(best, solve(idx));
  }while(next_permutation(all(idx)));
  cout << best << endl;
  return 0;
}

```