32030번 - 두 배

문제

밍구는 차세대 채팅 앱 ChatChatA을 개발했다!

ChatChatA를 배포하고 나니, 치명적인 버그 리포트가 밍구에게 날아왔다! 메시지를 입력하는 과정에서, 메시지의 마지막 글자가 특정 글자일 때, 특정 글자를 입력하면 메시지가 “두 배” 된다는 것이다!

정확히 풀어 설명하면 “두 배” 된다는 것은 다음과 같다.

• 현재 입력 중인 메시지를 M, M의 마지막 글자를 s, 입력할 글자를 c라고 하자.
• 메시지가 “두 배” 되는 (s, c) 쌍의 집합을 D라 하자.
  • (s, c) ∈ D 이면, c를 입력했을 때 M은 M + c가 아닌 M + M + c가 된다!
  • (s, c) ∉ D이면, c를 입력했을 때 M은 M + c가 된다.
• M이 빈 문자열이라면, M은 “두 배” 되지 않는다.

ChatChatA의 사용자인 구밍이는 문자열 T를 입력하기 위한 최소의 입력 수가 궁금해졌다.

현재 메시지 M은 빈 문자열로 시작하고, 매 입력은 다음 두 행동 중 하나이다.

• M에 문자 c를 추가한다. 위 조건에 따라서 메시지가 “두 배” 될 수 있다.
• M의 마지막 글자를 삭제한다. 단, M이 빈 문자열이 아닐 때에만 이 행동을 선택할 수 있다.

현재 메시지 M이 T가 되기 위한 최소의 입력 수를 구밍이 대신 구해주자!

입력

첫 줄에 D의 크기 N이 주어진다. (1 ≤ N ≤ 676 = 26²)

둘째 줄에 길이 N의 영어 소문자 문자열 S, 셋째 줄에 길이 N의 영어 소문자 문자열 C가 주어진다.

S의 i번째 글자를 S_i, C의 i번째 글자를 C_i라고 하면, D = {(S_i, C_i) : 1 ≤ i ≤ N}이다.

|D| = N이다. 즉, 같은 (S_i, C_i) 쌍은 주어지지 않는다.

넷째 줄에 입력할 영어 소문자로 이루어진 문자열 T가 주어진다. (1 ≤ |T| ≤ 500 000)

출력

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

만약 현재 메시지를 T로 만들지 못한다면 −1을 출력한다.

제한

힌트