B. Grand Renaming
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On the monorail line, there are $$$n$$$ stations, numbered in order from $$$1$$$ to $$$n$$$.

Each station $$$i$$$ has a name $$$s_i$$$ — a string of no more than 20 Latin letters. Each letter is written on a separate nameplate.

As part of the urban infrastructure upgrade project, it was decided to rename all the stations to some new names. The order for renaming has already been signed and will take effect tomorrow. However, there is a problem: no one has had time to replace the names on the nameplates at the stations. Now it is your task.

Unfortunately, there is no time to make new nameplates. Therefore, the only possible option is to move the nameplates from one station to another.

Formally, in one operation, you can choose two indices $$$1 \le i, j \le n$$$, as well as any letter from the string $$$s_i$$$, and move that letter to any position in the string $$$s_j$$$. This operation takes $$$1 + |i - j|$$$ precious units of time.

For example, if $$$s_i = \texttt{ab}$$$ and $$$s_j = \texttt{cd}$$$, then in one operation of moving a letter from $$$i$$$ to $$$j$$$, you can do:

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

Note that it is also allowed to choose $$$i = j$$$ in the operation.

You need to replace the nameplates with names at each station as quickly as possible so that they correspond to the new names. Determine whether this is possible, and if so, the minimum necessary amount of time.

Input

The first line of the test contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of stations on the line.

The second line of the test contains $$$n$$$ strings: $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le |s_i| \le 20$$$) — the original names of the stations.

The third line of the test contains $$$n$$$ strings: $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le |t_i| \le 20$$$) — the desired new names of the stations.

It is guaranteed that all strings in the test consist of lowercase Latin letters, characters from 'a' to 'z'.

Output

If there is no way to rename all the stations, output $$$-1$$$ in a single line. Otherwise, output a single number: the minimum possible total time required for the renaming operations.

Scoring
GroupPointsAdditional constraints Required groups
114$$$n = 1$$$–
217$$$\operatorname{sorted}(s_i) = \operatorname{sorted}(t_i) $$$–
325$$$s_i$$$ and $$$t_i$$$ have no common letters–
413$$$n \leq 1000; |s_i|, |t_i| \leq 10$$$–
511$$$|s_i| = 1$$$, $$$|t_i| = 1$$$–
611All strings consist of the letter a–
79–1–6

Here, $$$\operatorname{sorted}(s_i)$$$ denotes the string $$$s_i$$$ sorted in alphabetical order. For example, $$$\operatorname{sorted}(\texttt{abacaba}) = \texttt{aaaabbc}$$$

Examples
Input
3
no iislop nepon
inno polis open
Output
10
Input
3
eleven plus two
twelve plus one
Output
12
Input
1
evil
live
Output
3
Input
2
a b
ba ab
Output
-1
Input
2
indian cat
init canada
Output
-1
Input
4
aaaa aaa aa a
a aa aaa aaaa
Output
14
Input
7
s e a s i d e
d i s e a s e
Output
22