#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

const int MAX = 2005;
bool d[3][3][MAX];

int main(){
  vector<string> s(3); 
  for(int i = 0; i < 3; ++i)cin >> s[i];
  sort(s.begin(), s.end()); 
  int ans = MAX * 3;
  do{
    rep(i, 3)rep(j, 3)rep(k, s[i].size()){
      if(i >= j)continue; 
      bool is_ok = true;
      for(int ni = k; ni < s[i].size(); ++ni){ 
        int nj = ni - k; 
        if(nj >= s[j].size())break;
        if(s[i][ni] == '?' || s[j][nj] == '?')continue;
        if(s[i][ni] != s[j][nj])is_ok = false;
      }
      d[i][j][k] = is_ok;
    }

    auto f = [&](int i, int j, int k){
      if(k >= s[i].size())return true;
      return d[i][j][k];
    };
    rep(x, MAX)rep(y, MAX){
      if(!f(0, 1, x))continue;
      if(!f(1, 2, y))continue;
      if(!f(0, 2, x + y))continue;
      int now = 0;
      now = max({s[0].size(), x + s[1].size(), x + y + s[2].size()});
      ans = min(ans, now);
    }
  }while(next_permutation(s.begin(), s.end())); 

  cout << ans << endl;

  return 0;
}

### Prompt

Create a solution in cpp for 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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

const int MAX = 2005;
bool d[3][3][MAX];

int main(){
  vector<string> s(3); 
  for(int i = 0; i < 3; ++i)cin >> s[i];
  sort(s.begin(), s.end()); 
  int ans = MAX * 3;
  do{
    rep(i, 3)rep(j, 3)rep(k, s[i].size()){
      if(i >= j)continue; 
      bool is_ok = true;
      for(int ni = k; ni < s[i].size(); ++ni){ 
        int nj = ni - k; 
        if(nj >= s[j].size())break;
        if(s[i][ni] == '?' || s[j][nj] == '?')continue;
        if(s[i][ni] != s[j][nj])is_ok = false;
      }
      d[i][j][k] = is_ok;
    }

    auto f = [&](int i, int j, int k){
      if(k >= s[i].size())return true;
      return d[i][j][k];
    };
    rep(x, MAX)rep(y, MAX){
      if(!f(0, 1, x))continue;
      if(!f(1, 2, y))continue;
      if(!f(0, 2, x + y))continue;
      int now = 0;
      now = max({s[0].size(), x + s[1].size(), x + y + s[2].size()});
      ans = min(ans, now);
    }
  }while(next_permutation(s.begin(), s.end())); 

  cout << ans << endl;

  return 0;
}

```