Мальчик Валера очень любит строки. А еще больше он любит, когда строки одинаковые. Поэтому на досуге Валера сам с собой играет в следующую игру. Он берет две произвольные строки, состоящие из строчных букв латинского алфавита, и пытается сделать из них две равные друг другу. По правилам его игры, во время очередного хода Валере разрешается заменить в одной из строк один произвольный символ Ai на произвольный символ Bi, но при этом за каждый свой ход ему придется заплатить некоторую сумму денег, равную Wi. Ходов разрешается сделать бесконечно много. Поскольку Валера очень экономный мальчик и никогда не тратит свои деньги зря, он попросил Вас, как опытного программиста, помочь ему ответить на вопрос: какое наименьшее количество денег должно быть у Валеры, чтобы он смог получить одинаковые строки.
Выходные данные
Если решение существует, выведите в выходной файл ответ на задачу, а также получившуюся строку. В противном случае в единственной строке выведете -1. Если оптимальных решений несколько, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
uayd
uxxd
3
a x 8
x y 13
d c 3
|
21
uxyd
|
|
2
|
a
b
3
a b 2
a b 3
b a 5
|
2
b
|
|
3
|
abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0
|
-1
|