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.