← 返回题目列表

AtCoder · panasonic2020_e

E. 三个子串

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

Snuke 有一根绳子 s。 从这个字符串中,Anuke、Bnuke 和 Cnuke 获得了字符串 a, b,和 c分别如下:

  • 选择一个非空(连续)子字符串 s (可能 s 本身)。然后,将其中的一些字符(可能全部或没有)替换为 ?s。

例如,如果 s is mississippi,我们可以选择子字符串 ssissip 并替换其 1-st 和 3-rd 字符 ? 获取 ?s?ssip.

给你字符串 a, b,和 c。 找出最小可能长度 s.

约束

  • 1 \leq |a|, |b|, |c| \leq 2000
  • a, b,和 c 由小写英文字母和 ?s。

输入

输入由标准输入按以下格式给出:

a
b
c

输出

打印最小可能长度 s.


样本输入 1

a?c
der
cod

示例输出 1

7

例如, s 可能是 atcoder.


示例输入 2

atcoder
atcoder
???????

示例输出 2

7

a, b,和 c 可能不明显。