밍구는 차세대 채팅 앱 ChatChatA을 개발했다!
ChatChatA를 배포하고 나니, 치명적인 버그 리포트가 밍구에게 날아왔다! 메시지를 입력하는 과정에서, 메시지의 마지막 글자가 특정 글자일 때, 특정 글자를 입력하면 메시지가 "두 배" 된다는 것이다!
정확히 풀어 설명하면 "두 배" 된다는 것은 다음과 같다.
- 현재 입력 중인 메시지를 $M$, $M$의 마지막 글자를 $s$, 입력할 글자를 $c$라고 하자.
- 메시지가 "두 배" 되는 $(s, c)$ 쌍의 집합을 $D$라 하자.
- $ (s, c) \in D $ 이면, $c$를 입력했을 때 $M$은 $M + c$가 아닌 $M + M + c$가 된다!
- $ (s, c) \notin D $이면, $c$를 입력했을 때 $M$은 $M + c$가 된다.
- $M$이 빈 문자열이라면, $M$은 "두 배" 되지 않는다.
ChatChatA의 사용자인 구밍이는 문자열 $T$를 입력하기 위한 최소의 입력 수가 궁금해졌다.
현재 메시지 $M$은 빈 문자열로 시작하고, 매 입력은 다음 두 행동 중 하나이다.
- $M$에 문자 $c$를 추가한다. 위 조건에 따라서 메시지가 "두 배" 될 수 있다.
- $M$의 마지막 글자를 삭제한다. 단, $M$이 빈 문자열이 아닐 때에만 이 행동을 선택할 수 있다.
현재 메시지 $M$이 $T$가 되기 위한 최소의 입력 수를 구밍이 대신 구해주자!
Input
첫 줄에 $D$의 크기 $N$이 주어진다. ($1 \le N \le 676 = 26^2$)
둘째 줄에 길이 $N$의 영어 소문자 문자열 $S$, 셋째 줄에 길이 $N$의 영어 소문자 문자열 $C$가 주어진다.
$S$의 $i$번째 글자를 $S_i$, $C$의 $i$번째 글자를 $C_i$라고 하면, $D=\{(S_i, C_i) : 1 \le i \le N\}$이다.
$|D|=N$이다. 즉, 같은 $(S_i, C_i)$ 쌍은 주어지지 않는다.
넷째 줄에 입력할 영어 소문자로 이루어진 문자열 $T$가 주어진다. ($1 \le |T| \le 500\,000$)
Output
첫 줄에 현재 메시지를 $T$로 만드는 데 필요한 최소의 입력 수를 출력한다.
만약 현재 메시지를 $T$로 만들지 못한다면 $-1$을 출력한다.
Examples
Input 1
1 t a chatchata
Output 1
5
Input 2
2 ct ha chatchata
Output 2
-1
Input 3
2 af bd aafaaafaafaaafd
Output 3
8