몸값 요구서

알루미늄 외장재와 문, 창문 업계의 거물 Gilbert Bates가 납치되었다. 여러분은 납치범들이 몸값 요구서를 만드는 것을 도와야 한다. 재료는 신문 지면의 글과 몸값 요구서의 문장이다. 요구서는 신문에서 글자(또는 글자들의 연속, 경우에 따라 공백을 포함)를 오려 내어 빈 종이에 붙여 문장을 완성하는 방식으로 만든다. 요구서를 완성하기 위해 오려서 붙여야 하는 조각의 최소 개수를 구하라. 요구서에서 인접한 두 단어 사이에는, 한 조각이 그 사이의 공백을 포함하고 있거나, 아니면 두 조각 사이에 경계(빈틈)가 놓여 바탕의 흰 여백이 공백처럼 드러나야 한다.

첫 번째 줄은 몸값 요구서의 문장이다. 길이가 $2,048$자 미만인 한 줄이며, 구두점 없이 모두 소문자로 쓰여 있고 단어는 하나의 공백으로 구분된다. 그다음 줄부터는 신문 지면의 글이며, 대문자와 소문자, 구두점, 줄바꿈이 섞여 있고 길이는 $9,217$자 미만이다. 글자를 맞출 때 대소문자는 무시한다. 구두점과 줄바꿈은 절대 오릴 수 없으므로, 한 조각은 언제나 신문에서 잘라 낸 연속된 글자와 공백의 나열이다. 납치범들은 같은 신문을 여러 부 가지고 있어, 동일하거나 겹치는 부분을 필요한 만큼 몇 번이든 오릴 수 있다. 알파벳의 모든 글자는 신문에 적어도 한 번씩 나타난다.

전체 테스트의 60% 이상에서 신문의 길이는 $2,048$자 미만이다.

신문에서 오려 내어 요구서를 완성하는 데 필요한 조각의 최소 개수를 정수 하나로 출력한다.