두 배

밍구는 차세대 채팅 앱 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$로 만드는 데 필요한 최소 입력 수를 구밍이를 대신해 구해 보자.

첫 줄에 $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$)

첫 줄에 현재 메시지를 $T$로 만드는 데 필요한 최소 입력 수를 출력한다.

현재 메시지를 $T$로 만들 수 없다면 $-1$을 출력한다.