암호문 해독

문제

정보부에서 적의 암호문을 가로챘다. 이 암호문은 단어를 공백 없이 붙여 쓴 것이다. 각 단어는 0번 이상 나타날 수 있다.

이 암호 체계의 특징은 단어의 문자 순서를 바꿔 쓸 수 있다는 것이다. 이때, 원래 단어와 다른 위치에 있는 문자의 개수가 변환 비용이 된다. 순서를 바꾼 단어는 원래 단어와 같은 문자들을 같은 개수만큼 포함해야 한다. 즉, 두 단어의 길이와 각 알파벳의 등장 횟수가 모두 일치해야 한다.

예를 들어, abc는 비용 0으로 쓸 수 있고, acb, cba, bac는 비용 2, bca, cab는 비용 3이다. 사전과 암호문이 주어졌을 때, 암호문을 해석하는 데 필요한 최소 비용을 구하라.

입력

첫째 줄에 암호문이 주어진다. 암호문의 길이는 1 이상 50 이하이며, 소문자 알파벳으로만 구성된다.

둘째 줄에 사전에 있는 단어의 수 N이 주어진다. (1 ≤ N ≤ 50)

셋째 줄부터 N개의 줄에 사전에 있는 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 1 이상 50 이하이며, 소문자 알파벳으로만 구성된다.

출력

암호문을 사전에 있는 단어들로 분할하고 각 단어를 원래 단어로 복원하는 데 필요한 최소 변환 비용을 출력한다. 암호문을 사전의 단어들로 완전히 분할할 수 없으면 -1을 출력한다.

입출력 예시

입력 1

neotowheret
4
one
two
three
there

출력 1

8

입력 2

abba
3
ab
ac
ad

출력 2

2

입력 3

thisismeaningless
3
this
is
meaningful

출력 3

-1

입력 4

ogodtsneeencs
6
go
good
do
sentences
tense
scen

출력 4

8