У Магистра Максимуса в руках три артефакта с последовательностями символов. Чтобы раскрыть их тайны, нужно открыть все три артефакта одновременно с помощью одинаковых последовательностей символов. Для этого Максимус может удалять только самый правый символ из каждой последовательности сколько угодно раз. Обратите внимание, что для того, чтобы Максимус мог удалить символ из последовательности, ее длина должна быть не менее двух символов.
Определите минимальное количество операций, которые необходимо выполнить Максимусу, чтобы привести три последовательности к одинаковому виду. Если такое невозможно, ответ должен быть -1.
Входные данные
Программа получает на вход три строки s1, s2, s3 - последовательности символов, записанные на каждом из артефактов.
Constraints:
1 <= |s1|, |s2|, |s3| <= 100
s1, s2 и s3 состоят только из строчных английских букв
|s| означает длину последовательности
s
Выходные данные
Выведите ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
abb
ab
|
2
|
|
2
|
dac
bac
cac
|
-1
|