B. Грандиозное переименование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На линии монорельса находятся $$$n$$$ станций, пронумерованных по порядку от $$$1$$$ до $$$n$$$.

У каждой станции $$$i$$$ есть название $$$s_i$$$ — строка из не более 20 латинских букв. Каждая буква написана на отдельной табличке.

В ходе проекта обновления городской инфраструктуры было принято решение переименовать все станции в некоторые новые названия. Приказ о переименовании уже подписан и вступит в силу с завтрашнего дня. Но вот беда: на самих станциях никто не успел заменить названия на новые. Теперь это ваша задача.

Увы, времени на изготовление новых табличек нет. Поэтому единственная возможная опция — переместить таблички с одних станций на другие.

Формально за одну операцию вы можете выбрать два индекса $$$1 \le i, j \le n$$$, а также любую букву из строки $$$s_i$$$, и перенести эту букву в любое место строки $$$s_j$$$. Такая операция занимает $$$1 + |i - j|$$$ ценнейших единиц времени.

Например, если $$$s_i = \texttt{ab}$$$ и $$$s_j = \texttt{cd}$$$, то за одну операцию переноса буквы из $$$i$$$ в $$$j$$$ можно сделать:

  • $$$s_i = \texttt{a}$$$; $$$s_j = \texttt{bcd}$$$ или $$$s_j = \texttt{cbd}$$$ или $$$s_j = \texttt{cdb}$$$.
  • $$$s_i = \texttt{b}$$$; $$$s_j = \texttt{acd}$$$ или $$$s_j = \texttt{cad}$$$ или $$$s_j = \texttt{cda}$$$.

Обратите внимание, что в операции также разрешено выбирать $$$i = j$$$.

Вам нужно как можно быстрее заменить таблички с названиями на каждой станции, чтобы они соответствовали новым названиям. Определите возможно ли это, и если да, минимальное необходимое количество единиц времени.

Входные данные

Первая строка теста содержит единственное число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество станций на линии.

Вторая строка теста содержит $$$n$$$ строк: $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le |s_i| \le 20$$$) — изначальные названия станций.

Третья строка теста содержит $$$n$$$ строк: $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le |t_i| \le 20$$$) — желаемые новые названия станций.

Гарантируется что все строки в тесте состоят из маленьких латинских букв, символы от 'a' до 'z'.

Выходные данные

Если не существует способа переименовать все станции, в единственной строке выведите $$$-1$$$. Иначе, выведите одно число: минимально возможное суммарное время выполнения операций для переименования.

Система оценки
ГруппаБаллыДоп. ограничения Необходимые группы
114$$$n = 1$$$–
217$$$\operatorname{sorted}(s_i) = \operatorname{sorted}(t_i) $$$–
325$$$s_i$$$ и $$$t_i$$$ не имеют общих букв–
413$$$n \leq 1000; |s_i|, |t_i| \leq 10$$$–
511$$$|s_i| = 1$$$, $$$|t_i| = 1$$$–
611Все строки состоят из буквы a–
79–1–6

Здесь, $$$\operatorname{sorted}(s_i)$$$ обозначает отсортированную в алфавитном порядке строку $$$s_i$$$. Например, $$$\operatorname{sorted}(\texttt{abacaba}) = \texttt{aaaabbc}$$$.

Примеры
Входные данные
3
no iislop nepon
inno polis open
Выходные данные
10
Входные данные
3
eleven plus two
twelve plus one
Выходные данные
12
Входные данные
1
evil
live
Выходные данные
3
Входные данные
2
a b
ba ab
Выходные данные
-1
Входные данные
2
indian cat
init canada
Выходные данные
-1
Входные данные
4
aaaa aaa aa a
a aa aaa aaaa
Выходные данные
14
Входные данные
7
s e a s i d e
d i s e a s e
Выходные данные
22