CF822E.Liar

The first semester ended. You know, after the end of the first semester the holidays begin. On holidays Noora decided to return to Vičkopolis. As a modest souvenir for Leha, she brought a sausage of length m from Pavlopolis. Everyone knows that any sausage can be represented as a string of lowercase English letters, the length of which is equal to the length of the sausage.

Leha was very pleased with the gift and immediately ate the sausage. But then he realized that it was a quite tactless act, because the sausage was a souvenir! So the hacker immediately went to the butcher shop. Unfortunately, there was only another sausage of length n in the shop. However Leha was not upset and bought this sausage. After coming home, he decided to cut the purchased sausage into several pieces and number the pieces starting from 1 from left to right. Then he wants to select several pieces and glue them together so that the obtained sausage is equal to the sausage that Noora gave. But the hacker can glue two pieces together only when the number of the left piece is less than the number of the right piece. Besides he knows that if he glues more than x pieces, Noora will notice that he has falsified souvenir sausage and will be very upset. Of course Leha doesn’t want to upset the girl. The hacker asks you to find out whether he is able to cut the sausage he bought, and then glue some of the pieces so that Noora doesn't notice anything.

Formally, you are given two strings s and t. The length of the string s is n, the length of the string t is m. It is required to select several pairwise non-intersecting substrings from s, so that their concatenation in the same order as these substrings appear in s, is equal to the string t. Denote by f(s, t) the minimal number of substrings to be chosen so that their concatenation is equal to the string t. If it is impossible to choose such substrings, then f(s, t) = ∞. Leha really wants to know whether it’s true that f(s, t) ≤ x.

第一学期结束了。你知道，第一学期结束后便是假期。假期期间，努拉决定回到维奇科波利斯。作为送给列哈的一份朴素纪念品，她从帕夫洛波利斯带来了一根长度为 $m$ 的香肠。众所周知，任何香肠都可以表示为一个由小写英文字母组成的字符串，其长度等于香肠的长度。

列哈对这份礼物非常高兴，并立刻吃掉了这根香肠。但随后他意识到，这一举动十分失礼，因为这根香肠可是纪念品！于是这位黑客立即赶往肉铺。不幸的是，店里只剩下另一根长度为 $n$ 的香肠。然而列哈并未沮丧，还是买下了这根香肠。回家后，他决定将买来的香肠切成若干段，并从左至右依次将这些段编号为 $1, 2, \dots$。接着，他打算从中选出若干段并按编号递增顺序（即左段编号小于右段编号）将它们首尾粘合起来，使得最终得到的香肠字符串恰好等于努拉所赠的那根香肠。此外，他还知道：若粘合的段数超过 $x$ 段，努拉便会察觉纪念品香肠被伪造，从而非常生气。当然，列哈绝不想让姑娘生气。这位黑客请你帮忙判断：他是否能恰当地切割所购香肠，再从中选出若干段粘合，从而让努拉毫无察觉。

形式化地，给定两个字符串 $s$ 和 $t$，其中字符串 $s$ 的长度为 $n$，字符串 $t$ 的长度为 $m$。要求从 $s$ 中选出若干个两两不相交的子串（即在 $s$ 中互不重叠），并将它们按照在 $s$ 中出现的先后顺序拼接起来，使得拼接结果恰好等于字符串 $t$。记 $f(s,\,t)$ 为满足上述条件所需选取的最小子串数目；若不存在这样的子串选取方案，则令 $f(s,\,t) = \infty$。列哈迫切想知道是否成立：$f(s,\,t) \leq x$。

The first line contains single integer n (1 ≤ n ≤ 105) — length of sausage bought by Leha, i.e. the length of the string s.

The second line contains string s of the length n consisting of lowercase English letters.

The third line contains single integer m (1 ≤ m ≤ n) — length of sausage bought by Noora, i.e. the length of the string t.

The fourth line contains string t of the length m consisting of lowercase English letters.

The fifth line contains single integer x (1 ≤ x ≤ 30) — the maximum number of pieces of sausage that Leha can glue so that Noora doesn’t notice anything.

第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——Leha 购买的香肠长度，即字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。

第三行包含一个整数 $m$（$1 ≤ m ≤ n$）——Noora 购买的香肠长度，即字符串 $t$ 的长度。

第四行包含一个长度为 $m$ 的字符串 $t$，由小写英文字母组成。

第五行包含一个整数 $x$（$1 ≤ x ≤ 30$）——Leha 最多可以拼接的香肠段数，使得 Noora 不会察觉异常。

In the only line print "YES" (without quotes), if Leha is able to succeed in creating new sausage so that Noora doesn't notice anything. Otherwise print "NO" (without quotes).

在唯一的一行中，如果 Leha 能够成功制作出新的香肠，使得 Noora 注意不到任何异常，则输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

Let's consider the first sample.

In the optimal answer, Leha should cut the sausage he bought in the following way: hloyaygrt = h + loy + a + y + g + rt. Then he numbers received parts from 1 to 6:

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

Hereupon the hacker should glue the parts with numbers 2, 4 and 6 and get sausage loyygrt equal to one that is given by Noora. Thus, he will have to glue three pieces. Since x = 3 you should print "YES" (without quotes).

In the second sample both sausages coincide with sausages from the first sample. However since x = 2 you should print "NO" (without quotes).

我们来考虑第一个样例。

在最优方案中，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 的部分，从而得到香肠 loyygrt，其结果与 Noora 给出的香肠完全一致。因此，他总共需要粘合三段。由于 $x = 3$，你应输出 "YES"（不带引号）。

在第二个样例中，两条香肠均与第一个样例中的香肠相同。但由于 $x = 2$，你应输出 "NO"（不带引号）。