// ※※※ 解答不能 ※※※
// https://img.atcoder.jp/panasonic2020/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAX = 101010;
const int K = 50000;
#define M 4000
bool ab[MAX], ac[MAX], bc[MAX];

// 文字を比較する.
// @param c1: 対象文字.
// @param c2: 比較文字.
// @return  : 比較した結果.
bool match(char c1, char c2){
    return (c1 == '?' || c2 == '?' || c1 == c2);
}

int main(){
    
    // 1. 入力情報.
    char c1[2020], c2[2020], c3[2020];
    scanf("%s %s %s", c1, c2, c3);
    string a(c1), b(c2), c(c3);
    
    // 2. 各配列の更新.
    int al = a.size(), bl = b.size(), cl = c.size();
    rep(i, al) rep(j, bl) if(!match(a[i], b[j])) ab[i - j + K] = 1;
    rep(i, al) rep(j, cl) if(!match(a[i], c[j])) ac[i - j + K] = 1;
    rep(i, bl) rep(j, cl) if(!match(b[i], c[j])) bc[i - j + K] = 1;
    
    // 3. 長さを計算.
    int ans = 123456789;
    repx(i, -M, M + 1){
        repx(j, -M, M + 1){
            if(!ab[i + K] && !ac[j + K] && !bc[j - i + K]){
                int L = min(0, min(i, j));
                int R = max(al, max(bl + i, cl + j));
                ans = min(ans, R - L);
            }
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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
// ※※※ 解答不能 ※※※
// https://img.atcoder.jp/panasonic2020/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAX = 101010;
const int K = 50000;
#define M 4000
bool ab[MAX], ac[MAX], bc[MAX];

// 文字を比較する.
// @param c1: 対象文字.
// @param c2: 比較文字.
// @return  : 比較した結果.
bool match(char c1, char c2){
    return (c1 == '?' || c2 == '?' || c1 == c2);
}

int main(){
    
    // 1. 入力情報.
    char c1[2020], c2[2020], c3[2020];
    scanf("%s %s %s", c1, c2, c3);
    string a(c1), b(c2), c(c3);
    
    // 2. 各配列の更新.
    int al = a.size(), bl = b.size(), cl = c.size();
    rep(i, al) rep(j, bl) if(!match(a[i], b[j])) ab[i - j + K] = 1;
    rep(i, al) rep(j, cl) if(!match(a[i], c[j])) ac[i - j + K] = 1;
    rep(i, bl) rep(j, cl) if(!match(b[i], c[j])) bc[i - j + K] = 1;
    
    // 3. 長さを計算.
    int ans = 123456789;
    repx(i, -M, M + 1){
        repx(j, -M, M + 1){
            if(!ab[i + K] && !ac[j + K] && !bc[j - i + K]){
                int L = min(0, min(i, j));
                int R = max(al, max(bl + i, cl + j));
                ans = min(ans, R - L);
            }
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
}
```