17233번 - 문자열 장식 서브태스크

바야흐로 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명의 소학회원이 원하는 문자열 P₁…P_N을 모두 부분 문자열로 가지면서 가장 짧은 S의 부분 문자열을 주문하려고 한다. 이때 만영이가 주문하게 될 문자열의 길이를 구해보자.

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

S는 P₁…P_N을 모두 부분 문자열로 갖는다.

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

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

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