E - Three Substrings /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

すぬけ君は、文字列 s を持っています。 あぬけ君、ぶぬけ君、くぬけ君は次のような方法でそれぞれ文字列 a, b, c を得ました。

  • s の空でない (s 全体であってもよい) 連続な部分文字列を一つ選ぶ。その部分文字列のうちいくつかの文字 (0 個や全部であってもよい) を ? で置き換える。

たとえば、smississippi であるとき、部分文字列として ssissip を選び、その 1, 3 文字目を ? で置き換えることで ?s?ssip を得ることができます。

文字列 a, b, c が与えられます。 s の長さとして考えられる最小値を求めてください。

制約

  • 1 \leq |a|, |b|, |c| \leq 2000
  • a, b, c は英小文字と ? からなる。

入力

入力は以下の形式で標準入力から与えられる。

a
b
c

出力

s の長さとして考えられる最小値を出力せよ。


入力例 1

a?c
der
cod

出力例 1

7

たとえば、satcoder のとき条件を満たします。


入力例 2

atcoder
atcoder
???????

出力例 2

7

a, b, c は相異なるとは限りません。

Score : 500 points

Problem Statement

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.


Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.


Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.