/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
すぬけ君は、文字列 s を持っています。 あぬけ君、ぶぬけ君、くぬけ君は次のような方法でそれぞれ文字列 a, b, c を得ました。
- s の空でない (s 全体であってもよい) 連続な部分文字列を一つ選ぶ。その部分文字列のうちいくつかの文字 (0 個や全部であってもよい) を
?で置き換える。
たとえば、s が mississippi であるとき、部分文字列として 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
たとえば、s が atcoder のとき条件を満たします。
入力例 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.