#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  int la = a.length();
  int lb = b.length();
  int lc = c.length();
  int ans = la + lb + lc;
  int lbc = lb + lc;
  string q = "";
  rep(i,lbc) q += "?";
  a = q + a + q;
  la = a.length();
  vector<bool> bf(la,false);
  vector<bool> cf(la,false);
  vector<bool> bcf(lbc,false);
  for(int i = 0; i + lb <= la; i++) {
    bool f = true;
    rep(j,lb) {
      if(a[i+j] != '?' && b[j] != '?' && a[i+j] != b[j]) f = false;
    }
    if(f) bf[i] = true;
  }
   for(int i = 0; i + lc <= la; i++) {
    bool f = true;
    rep(j,lc) {
      if(a[i+j] != '?' && c[j] != '?' && a[i+j] != c[j]) f = false;
    }
    if(f) cf[i] = true;
  };
  for(int i = -lc+1; i < lb; i++) {
    bool f = true;
    rep(j,lc) {
      if(i+j >= 0 && i+j < lb && b[i+j] != '?' && c[j] != '?' && b[i+j] != c[j]) f = false;
    }
    if(f) bcf[i+lc] = true;
    else bcf[i+lc] = false;
  }
  rep(i,la) {
    rep(j,la) {
      if(j-i >= -lc+1 && j-i < lb) {
        if(bcf[j-i+lc] && bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      } else {
        if(bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      }
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp 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 < (int)n; i++)
using ll = long long;

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  int la = a.length();
  int lb = b.length();
  int lc = c.length();
  int ans = la + lb + lc;
  int lbc = lb + lc;
  string q = "";
  rep(i,lbc) q += "?";
  a = q + a + q;
  la = a.length();
  vector<bool> bf(la,false);
  vector<bool> cf(la,false);
  vector<bool> bcf(lbc,false);
  for(int i = 0; i + lb <= la; i++) {
    bool f = true;
    rep(j,lb) {
      if(a[i+j] != '?' && b[j] != '?' && a[i+j] != b[j]) f = false;
    }
    if(f) bf[i] = true;
  }
   for(int i = 0; i + lc <= la; i++) {
    bool f = true;
    rep(j,lc) {
      if(a[i+j] != '?' && c[j] != '?' && a[i+j] != c[j]) f = false;
    }
    if(f) cf[i] = true;
  };
  for(int i = -lc+1; i < lb; i++) {
    bool f = true;
    rep(j,lc) {
      if(i+j >= 0 && i+j < lb && b[i+j] != '?' && c[j] != '?' && b[i+j] != c[j]) f = false;
    }
    if(f) bcf[i+lc] = true;
    else bcf[i+lc] = false;
  }
  rep(i,la) {
    rep(j,la) {
      if(j-i >= -lc+1 && j-i < lb) {
        if(bcf[j-i+lc] && bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      } else {
        if(bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      }
    }
  }
  cout << ans << endl;
  return 0;
}

```