시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12 4 4 57.143%

문제

바야흐로 2019년. 아주대학교 알고리즘 소학회 A.N.S.I.는 드디어 동방을 배정받았다!

A.N.S.I. 소학회원들은 새로운 동방을 꾸미기 위해 각자의 예술혼을 불태웠는데, 문자열을 좋아하는 만영이는 벽에 문자열을 하나 장식하고 싶다. 하지만 흔하지 않은 수요라 구하지 못하던 중에, 만영이는 인터넷에서 어떤 문자열 S의 부분 문자열을 판매하는 가게를 찾았다.

부분 문자열이란 원본 문자열의 연속된 일부를 뜻한다. 예를 들어 "acka"의 부분 문자열은 {"", "a", "c", "k", "ac", "ck", "ka", "ack", "cka", "acka"}로 총 10가지가 있다.

만영이가 어떤 문자열이 좋을지 S를 훑고 있던 와중에 뒤에서 구경하던 몇몇 소학회원이 S의 부분 문자열 중 자신이 원하는 문자열을 말하기 시작했다.

  • 준서(현 회장): "저는 여기 보이는 'ansi'는 꼭 들어가 있으면 좋겠어요."
  • 준표(전 회장): "어 저기에 'spectacle'도 있네요. 저는 'spectacle'도 있으면 좋을 것 같아요."
  • 현정(전 전 회장): "그럼 이 'graduation'도 넣자."
  • ...
  • 지수(현 총무): "저는 뭐든 상관없으니까, 제발 예산 좀 아껴 써주세요.."

사람 좋은 선배인 만영이는 이들의 요청을 무시할 수 없기 때문에, 모든 문자열을 부분 문자열로 포함하는 문자열을 구매하려고 한다. 문자열의 가격은 문자열의 길이에 비례한다. 소학회 예산을 걱정하는 지수를 위해 만영이는 N명의 소학회원이 원하는 문자열 P1PN을 모두 부분 문자열로 가지면서 가장 짧은 S의 부분 문자열을 주문하려고 한다. 이때 만영이가 주문하게 될 문자열의 길이를 구해보자.

입력

첫 번째 줄에 N이 주어진다. 그 이후 2번째 줄부터 N+1번째 줄까지 P1부터 PN의 길이와 문자열이 순서대로 주어진다. 그 후 마지막 줄에 S의 길이와 S가 주어진다. 모든 문자열은 'a'부터 'z'까지의 소문자 알파벳으로만 이루어져 있다.

SP1PN을 모두 부분 문자열로 갖는다.

출력

조건을 만족하는 S의 부분 문자열의 최소 길이를 첫 줄에 출력한다.

서브태스크 1 (100점)

  • 0 < |S| ≤ 100,000
  • 0 < N ≤ 10
  • 0 < |Pi| ≤ 100

서브태스크 2 (40점)

  • 0 < |S| ≤ 500,000
  • 0 < N ≤ 100
  • 0 < |Pi| ≤ 10,000

예제 입력 1

4
2 an
4 anab
2 ab
4 nana
18 bananabananabanana

예제 출력 1

5

예제 입력 2

7
4 ajou
4 ajou
7 welcome
2 to
4 ajou
11 programming
7 contest
31 welcometoajouprogrammingcontest

예제 출력 2

31

예제 입력 3

2
7 insider
4 acka
53 superduperinsiderkinggodackaemperorgeneralchungmugong

예제 출력 3

18

아주대에는 전설로 내려오는 최강의 인싸가 존재한다.

채점

  • 예제는 채점하지 않는다.