#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;

ll mmax(ll a, ll b) {
  return a > b ? a : b;
}

int main(void) {
  ll i, j, k, l, m, n[3], ans = 1e4;
  char s[3][2010], tmp[6010];
  for(i = 0; i < 3; ++i) scanf("%s", s[i]), n[i] = strlen(s[i]);
  bool b[3][3][5000];
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) for(k = 0; k < 5000; ++k) b[i][j][k] = true;
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) for(k = 0; k < n[i]; ++k) {
    bool t = true;
    for(l = 0; l < (n[i] - k < n[j] ? n[i] - k : n[j]); ++l) if(s[i][k + l] != '?' && s[j][l] != '?' && s[i][k + l] != s[j][l]) t = false;
    b[i][j][k] = t;
  }
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) if(i != j) for(k = 0; k < 3; ++k) if(i != k && j != k) {
    for(l = 0; l <= n[i]; ++l) if(b[i][j][l]) for(m = 0; m <= mmax(n[j], n[i] - l); ++m) if(b[j][k][m] && b[i][k][l + m]) {
      if(ans > mmax(n[i], mmax(n[j] + l, n[k] + l + m))) ans = mmax(n[i], mmax(n[j] + l, n[k] + l + m));
    }
  }
  printf("%lld", ans);
  return 0;
}
### Prompt

Generate 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 <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;

ll mmax(ll a, ll b) {
  return a > b ? a : b;
}

int main(void) {
  ll i, j, k, l, m, n[3], ans = 1e4;
  char s[3][2010], tmp[6010];
  for(i = 0; i < 3; ++i) scanf("%s", s[i]), n[i] = strlen(s[i]);
  bool b[3][3][5000];
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) for(k = 0; k < 5000; ++k) b[i][j][k] = true;
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) for(k = 0; k < n[i]; ++k) {
    bool t = true;
    for(l = 0; l < (n[i] - k < n[j] ? n[i] - k : n[j]); ++l) if(s[i][k + l] != '?' && s[j][l] != '?' && s[i][k + l] != s[j][l]) t = false;
    b[i][j][k] = t;
  }
  for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) if(i != j) for(k = 0; k < 3; ++k) if(i != k && j != k) {
    for(l = 0; l <= n[i]; ++l) if(b[i][j][l]) for(m = 0; m <= mmax(n[j], n[i] - l); ++m) if(b[j][k][m] && b[i][k][l + m]) {
      if(ans > mmax(n[i], mmax(n[j] + l, n[k] + l + m))) ans = mmax(n[i], mmax(n[j] + l, n[k] + l + m));
    }
  }
  printf("%lld", ans);
  return 0;
}
```