마법 주문 조합

대마법사가 목표 문자열 S를 마법 주문으로 완성하려고 한다. 사용 가능한 마법 주문 N개가 주어지며, 각 주문은 특정 문자열과 일치한다.

목표 문자열 S를 주음악보의 주문들을 연속해서 배치하여 정확히 구성해야 한다. 각 주문은 여러 번 사용할 수 있으며, 주문들이 겹치지 않고 순서대로 배치되어야 한다.

목표 문자열 S를 완성하기 위해 필요한 최소 주문 수를 구하시오. 불가능한 경우 -1을 출력한다.

입력

첫째 줄에 목표 문자열 S가 주어진다. (1 <= |S| <= 100)
둘째 줄에 사용 가능한 주문의 수 N이 주어진다. (1 <= N <= 100)
셋째 줄부터 N개의 줄에 걸쳐 각 주문의 문자열이 주어진다. 각 주문의 길이는 1 이상 100 이하이며, 알파벳 소문자로만 이루어져 있다.

출력

목표 문자열을 완성하기 위한 최소 주문 수를 출력한다. 불가능하면 -1을 출력한다.

입출력 예시

입력 1

abcd
2
ab
cd

출력 1

2

입력 2

abcde
3
ab
cde
abc

출력 2

2