거짓말쟁이

첫 학기가 끝났다. 알다시피 첫 학기가 끝나면 방학이 시작된다. 방학 동안 Noora는 Vičkopolis로 돌아가기로 했다. Leha를 위한 소박한 기념품으로, Noora는 Pavlopolis에서 길이가 m인 소시지를 가져왔다. 모든 소시지는 소문자 영문자로 이루어진 문자열로 나타낼 수 있으며, 그 문자열의 길이는 소시지의 길이와 같다는 사실은 누구나 알고 있다.

Leha는 선물을 받고 매우 기뻐하여 곧바로 소시지를 먹었다. 하지만 소시지가 기념품이었으므로 그것이 상당히 무례한 행동이었다는 사실을 뒤늦게 깨달았다! 그래서 해커는 즉시 정육점으로 갔다. 안타깝게도 가게에는 길이가 n인 다른 소시지 하나만 있었다. However Leha는 실망하지 않고 이 소시지를 샀다. 집에 돌아온 뒤, 그는 구매한 소시지를 여러 조각으로 자르고 왼쪽부터 오른쪽까지 1부터 시작하여 조각에 번호를 매기기로 했다. 그런 다음 여러 조각을 골라 서로 붙여서, 완성된 소시지가 Noora가 준 소시지와 같게 만들고 싶어 한다. 하지만 해커는 왼쪽 조각의 번호가 오른쪽 조각의 번호보다 작을 때만 두 조각을 붙일 수 있다. 또한 x개보다 많은 조각을 붙이면 Noora가 기념품 소시지를 위조했다는 사실을 알아차리고 매우 속상해할 것임을 알고 있다. 물론 Leha는 그 소녀를 속상하게 하고 싶지 않다. 해커는 자신이 산 소시지를 자른 다음 일부 조각을 붙여 Noora가 아무것도 눈치채지 못하게 할 수 있는지 알아봐 달라고 한다.

형식적으로 두 문자열 s와 t가 주어진다. 문자열 s의 길이는 n이고, 문자열 t의 길이는 m이다. s에서 서로 겹치지 않는 여러 부분 문자열을 선택하여, 이 부분 문자열들이 s에 나타나는 순서대로 이어 붙인 결과가 문자열 t와 같아야 한다. 이어 붙인 결과가 문자열 t와 같아지도록 선택해야 하는 부분 문자열의 최소 개수를 f(s, t)라고 하자. 그러한 부분 문자열들을 선택하는 것이 불가능하면 f(s, t) = ∞이다. Leha는 f(s, t) ≤ x가 참인지 무척 알고 싶어 한다.

첫 번째 줄에는 정수 n (1 ≤ n ≤ 105) 하나가 주어진다. 이는 Leha가 산 소시지의 길이, 즉 문자열 s의 길이이다.

두 번째 줄에는 소문자 영문자로 이루어진 길이 n의 문자열 s가 주어진다.

세 번째 줄에는 정수 m (1 ≤ m ≤ n) 하나가 주어진다. 이는 Noora가 산 소시지의 길이, 즉 문자열 t의 길이이다.

네 번째 줄에는 소문자 영문자로 이루어진 길이 m의 문자열 t가 주어진다.

다섯 번째 줄에는 정수 x (1 ≤ x ≤ 30) 하나가 주어진다. 이는 Noora가 아무것도 눈치채지 못하도록 Leha가 붙일 수 있는 소시지 조각의 최대 개수이다.

Leha가 Noora에게 아무것도 들키지 않도록 새 소시지를 만드는 데 성공할 수 있다면 유일한 줄에 "YES"(따옴표 제외)를 출력한다. 그렇지 않으면 "NO"(따옴표 제외)를 출력한다.

첫 번째 예제를 살펴보자.

최적의 답에서 Leha는 자신이 산 소시지를 다음과 같이 잘라야 한다. hloyaygrt = h + loy + a + y + g + rt. 그런 다음 만들어진 조각에 1부터 6까지 번호를 매긴다.

• h — 번호 1
• loy — 번호 2
• a — 번호 3
• y — 번호 4
• g — 번호 5
• rt — 번호 6

그다음 해커는 번호가 2, 4, 6인 조각들을 붙여 Noora가 준 소시지와 같은 loyygrt 소시지를 만들어야 한다. 따라서 그는 세 조각을 붙여야 한다. x = 3이므로 "YES"(따옴표 제외)를 출력해야 한다.

두 번째 예제의 두 소시지는 첫 번째 예제의 소시지들과 같다. 하지만 x = 2이므로 "NO"(따옴표 제외)를 출력해야 한다.