쥐

주기적으로 반복되는 문자열 $A$가 덮인 무한한 직선이 주어진다. 직선에는 문자열 $A$가 무한히 이어 붙여져 있다. 직선에는 시작도 끝도 없다. 또 $M$개의 문자열로 이루어진 집합 $S$가 주어진다. $S$의 문자열을 이어 붙여 새로운 문자열 $B$를 만들어야 한다. $B$는 다음 조건을 만족해야 한다.

• 새로 만든 빈 무한 직선을 문자열 $B$의 무한한 반복으로 덮었을 때, 그 직선은 $A$로 덮은 직선과 같아야 한다.
• 조건을 만족하는 $B$나 $B$를 만드는 방법이 여러 가지라면, $S$에서 사용한 문자열의 개수가 최소가 되는 $B$와 그 만드는 방법을 선택한다.

$S$의 같은 문자열을 여러 번 사용할 수 있지만, 사용할 때마다 개수를 센다. 문자열은 아무 순서로나 이어 붙일 수 있지만, 문자열 안의 글자 순서는 바꿀 수 없다. 어떤 문자열 $B$도 만들 수 없다면 $-1$을 출력한다.

• 첫째 줄에 문자열 $A$가 주어진다. ($1\leq |A| \leq 500$)
• 둘째 줄에 정수 $M$이 주어진다. $M$은 집합 $S$에 들어 있는 문자열의 개수이다. ($1 \leq M \leq 10^5$)
• 다음 $M$개의 줄에 $S$의 문자열이 하나씩 주어진다. $i$번째 줄에는 문자열 $L_i$가 주어진다. ($1 \leq |L_i| \leq |A|$)
• $S$에 들어 있는 문자열 길이의 합은 $10^6$보다 작거나 같다. ($\sum_{i=1}^{M} |L_i| \leq 10^6$)

문자열 $B$를 만드는 데 필요한 $S$의 문자열 개수의 최솟값을 정수 하나로 출력한다.

문자열 "b" 하나와 "a" 두 개를 사용해 $B$ = "aba"를 만들 수 있다.

• ...baabaabaabaa...
• .....abaabaabaaba...